04260-medium-nomiwase
Back
type StringToUnion<S> = S extends `${infer F}${infer R}` ? F | StringToUnion<R> : S
type AllCombinations<
S extends string,
T extends string = StringToUnion<S>,
U extends string = T,
> = S extends `${infer F}${infer R}`
? U extends U
? `${U}${AllCombinations<R, U extends '' ? T : Exclude<T, U>>}`
: never
: ''
Solution by MyeonghoonNam
#31162
type ToLetters<S extends string> =
S extends `${infer F}${infer R}`
? F | ToLetters<R>
: never
type AllCombinations<
S extends string,
L extends string = '' | ToLetters<S>,
U extends string = L
> =
L extends U
? '' | `${L}${AllCombinations<never, Exclude<U, L>>}`
: never
Solution by sbr61
#30134
type StringToArray<S, L extends string[] = []> = S extends `${infer A}${infer B}` ? [A, ...StringToArray<B, L>] : L
type Combination<T extends string[], All = T[number], Item = All> = Item extends string ? Item | `${Item}${Combination<[], Exclude<All, Item>>}` : never
type AllCombinations<S> = '' | Combination<StringToArray<S>>
Solution by tclxshunquan-wang
#29848
type StrToUnion<T extends string> = T extends `${infer L}${infer R}`
? L | StrToUnion<R>
: T;
type AllCombinations<
S extends string,
U extends string = StrToUnion<S>,
All extends string = U
> = U extends U ? U | `${U}${AllCombinations<S, Exclude<All, U>>}` : never;
Solution by DoubleWoodLin
#28835
type StrToUnion<T extends string> = T extends `${infer L}${infer R}`
? L | StrToUnion<R>
: T;
type AllCombinations<S extends string, U extends string = StrToUnion<S>> = [
U
] extends [never]
? ""
:
| {
[K in U]: `${K}${AllCombinations<never, Exclude<U, K>>}`;
}[U]
|"";
Solution by DoubleWoodLin
#28738
// your answers
type StrToUnion<S extends string, R = never> = S extends `${infer F}${infer L}` ? StrToUnion<L, R | F> : R;
type AllCombinations<S extends string, U extends string = StrToUnion<S>> = [U] extends [never] ? '' : '' | {
[K in U]: `${K}${AllCombinations<never, Exclude<U, K>>}`
}[U];
Solution by CheolMinBae
#27241
This is an interesting approach that I tried that did not work. I have not yet taken a look at the other solutions but I suspect they make utility of converting strings to unions. I tried to do it in the string space.
I also created a debugging function in the form of a generic type that shows the permutations (i.e. combinations) which were left out by my implementation.
namespace Utilities {
export type C<S extends string> =
S extends `${infer First}${infer Rest}` ?
First | C<Rest> | `${C<Rest>}${First}` | `${First}${C<Rest>}` : ""
}
type AllCombinations<S extends string> = "" | Utilities.C<S>
type DebugAllCombinations<A extends string, B extends string> =
B extends AllCombinations<A> ? never : B
// this evaluates to "BAC" | "CAB"
type difference1 = DebugAllCombinations<'ABC', '' | 'A' | 'B' | 'C' | 'AB' | 'AC' | 'BA' | 'BC' | 'CA' | 'CB' | 'ABC' | 'ACB' | 'BAC' | 'BCA' | 'CAB' | 'CBA'>
// this evaluates to "BAC" | "CAB" | "BAD" | "CAD" | ...
type difference2 = DebugAllCombinations<'ABCD', '' | 'A' | 'B' | 'C' | 'D' | 'AB' | 'AC' | 'AD' | 'BA' | 'BC' | 'BD' | 'CA' | 'CB' | 'CD' | 'DA' | 'DB' | 'DC' | 'ABC' | 'ABD' | 'ACB' | 'ACD' | 'ADB' | 'ADC' | 'BAC' | 'BAD' | 'BCA' | 'BCD' | 'BDA' | 'BDC' | 'CAB' | 'CAD' | 'CBA' | 'CBD' | 'CDA' | 'CDB' | 'DAB' | 'DAC' | 'DBA' | 'DBC' | 'DCA' | 'DCB' | 'ABCD' | 'ABDC' | 'ACBD' | 'ACDB' | 'ADBC' | 'ADCB' | 'BACD' | 'BADC' | 'BCAD' | 'BCDA' | 'BDAC' | 'BDCA' | 'CABD' | 'CADB' | 'CBAD' | 'CBDA' | 'CDAB' | 'CDBA' | 'DABC' | 'DACB' | 'DBAC' | 'DBCA' | 'DCAB' | 'DCBA'>
Solution by diraneyya
#27154
type StringToUnion<S extends string> = S extends `${infer F}${infer Rest}` ? F | StringToUnion<Rest> : S
// type ProcessUnion<S extends string, Ret extends string = '', Acc extends string = S>
// = [ S ] extends [ never ] ? never
// : Acc extends any
// ? Ret | Acc | ProcessUnion<Exclude<S, Acc>, `${Ret}${Acc}`>
// : never
// type AllCombinations<S extends string> = ProcessUnion<StringToUnion<S>>
type AllCombinations<S extends string, Acc extends string = StringToUnion<S>>
= [ Acc ] extends [ never ] ? ''
: '' | { [ C in Acc ]: `${C}${AllCombinations<'', Exclude<Acc, C>>}` }[Acc]
Solution by tokyo9pm
#26781
type StringToUnion<S extends string> = S extends `${infer U}${infer Rest}` ? U | StringToUnion<Rest> : never
type Permutation<T, U=T> = [T] extends [never] ? [] : T extends U ? [T, ...Permutation<Exclude<U, T>>] : []
type PermutationComb<T, U=T> = (T extends U ? PermutationComb<Exclude<U, T>> : never) | Permutation<U>
type ArrToString<T> = T extends [] ? '' : T extends [infer F extends string, ...infer Rest] ? `${F}${ArrToString<Rest>}` : never
type AllCombinations<S extends string> = ArrToString<PermutationComb<StringToUnion<S>>>
Solution by enochjs
#25970
type StringToUnion<T extends string, R extends string[] = []> = T extends `${infer K}${infer U}`
? StringToUnion<U, [...R, K]>
: R[number] | "";
type Combination<T extends string, U = T> = U extends T
? U | `${U}${Combination<Exclude<T, U>>}`
: never;
type AllCombinations<S extends string> = Combination<StringToUnion<S>>;
Solution by yungo1846
#25640
// your answers
type StringToUnion<S extends string> = S extends `${infer A}${infer Rest}`
? A | StringToUnion<Rest>
: "";
type Combinations<T extends string, U = T> = U extends T
? U | `${U}${Combinations<Exclude<T, U>>}`
: never;
type AllCombinations<S extends string> = Combinations<StringToUnion<S>>;
Solution by kiki-zjq
#25225
4260 - AllCombinations
AllCombinations will make you want to cry when you read the description, but the solution is actually pretty easy (so long as you can launch your brain into a recursive 4th dimension).
🎥 Video Explanation
🔢 Code
// ============= Test Cases =============
import type { Equal, Expect } from "./test-utils";
type A1 = AllCombinations<"">;
type B1 = "";
type C1 = Expect<Equal<A1, B1>>;
type A2 = AllCombinations<"A">;
type B2 = "" | "A";
type C2 = Expect<Equal<A2, B2>>;
type A3 = AllCombinations<"AB">;
type B3 =
| "" | "A" | "B"
| "AB" | "BA"
;
type C3 = Expect<Equal<A3, B3>>;
type A4 = AllCombinations<"ABC">;
type B4 =
| ""
| "A"
| "B"
| "C"
| "AB" | "AC"
| "BA" | "BC"
| "CA" | "CB"
| "ABC" | "ACB"
| "BAC" | "BCA"
| "CAB" | "CBA"
;
type C4 = Expect<Equal<A4, B4>>;
type A5 = AllCombinations<"ABCD">;
type B5 =
| ""
| "A"
| "B"
| "C"
| "D"
| "AB" | "AC" | "AD"
| "BA" | "BC" | "BD"
| "CA" | "CB" | "CD"
| "DA" | "DB" | "DC"
| "ABC" | "ABD" | "ACB" | "ACD" | "ADB" | "ADC"
| "BAC" | "BAD" | "BCA" | "BCD" | "BDA" | "BDC"
| "CAB" | "CAD" | "CBA" | "CBD" | "CDA" | "CDB"
| "DAB" | "DAC" | "DBA" | "DBC" | "DCA" | "DCB"
| "ABCD" | "ABDC" | "ACBD" | "ACDB" | "ADBC" | "ADCB"
| "BACD" | "BADC" | "BCAD" | "BCDA" | "BDAC" | "BDCA"
| "CABD" | "CADB" | "CBAD" | "CBDA" | "CDAB" | "CDBA"
| "DABC" | "DACB" | "DBAC" | "DBCA" | "DCAB" | "DCBA"
;
type C5 = Expect<Equal<A5, B5>>;
// ============= Your Code Here =============
// previous challenge: 43
type Exclude<T, U> = T extends U ? never : T;
// previous challenge: 1042
type IsNever<T> = [T] extends [never] ? true : false;
// previous challenge: 531
type StringToUnion<T> =
T extends `${infer Head}${infer Tail}`
? Head | StringToUnion<Tail>
: never;
type AllCombinations<
S,
Acc extends string = StringToUnion<S>
> =
IsNever<Acc> extends true
? ""
: "" | {
[Combo in Acc]:
`${
Combo
}${
AllCombinations<
never,
Exclude<Acc, Combo>
>
}`
}[Acc];
// ============== Alternatives ==============
type StringToUnion<S extends string> =
S extends `${infer Head}${infer Tail}`
? Head | StringToUnion<Tail>
: S; // this variant doesn't return never
type Combination<A extends string, B extends string> =
| A
| B
| `${A}${B}`
| `${B}${A}`;
type UnionCombination<
A extends string,
B extends string = A
> =
A extends B
? Combination<A, UnionCombination<Exclude<B, A>>>
: never;
type AllCombinations<S extends string> =
UnionCombination<StringToUnion<S>>
type AllCombinations<
S extends string,
Acc extends string = ''
> =
S extends `${infer Head}${infer Tail}`
?
| `${Head}${AllCombinations<`${Acc}${Tail}`>}`
| AllCombinations<Tail, `${Acc}${Head}`>
: '';
➕ More Solutions
For more video solutions to other challenges: see the umbrella list! https://github.com/type-challenges/type-challenges/issues/21338
Solution by dimitropoulos
#24325
type SplitTo<T extends string> = T extends `${infer F}${infer R}` ? F | SplitTo<R> : ``;
type UnionComb<T extends string, U = T> = U extends T ? U | `${U}${UnionComb<Exclude<T, U>>}` : never;
type AllCombinations<S extends string> = UnionComb<SplitTo<S>>;
Solution by E-uler
#23945
type StringToUnion<S extends string> = S extends `${infer A}${infer Rest}`
? A | StringToUnion<Rest>
: "";
type Combinations<T extends string, U = T> = U extends T
? U | `${U}${Combinations<Exclude<T, U>>}`
: never;
type AllCombinations<S extends string> = Combinations<StringToUnion<S>>;
Solution by snakeUni
#22887
// your answers
type Combination<A extends string, B extends string> = A | B | `${A}${B}` | `${B}${A}`
type StringToUnion<Str extends string> = Str extends `${infer F}${infer Rest}` ? F | StringToUnion<Rest> : never;
type InAllCombinations<A extends string, B extends string = A> = A extends A ? Combination<A, AllCombinations<Exclude<B, A>>> : never;
type AllCombinations<S extends string> = InAllCombinations<StringToUnion<S>> | ''
Solution by jxhhdx
#22718
// eg. "abc" => "a" | "b" | "c"
type StringToCharsUnion<S, L = never> =
S extends `${infer F}${infer R}` ? StringToCharsUnion<R, L | F> : L;
// answer
type InnerAllCombinations<S, Path extends string, RU = never, SS = S> =
[S] extends [never]
? RU | Path
: S extends string // Distributive Conditional Types
? InnerAllCombinations<Exclude<SS, S>, `${Path}${S}`, RU | Path>
: RU;
type AllCombinations<S extends string> =
InnerAllCombinations<StringToCharsUnion<S>, "">;
Solution by coderyoo1
#22634
type StringToUnion<S extends string> = S extends `${infer A}${infer Rest}`
? A | StringToUnion<Rest>
: "";
type Combinations<T extends string, U = T> = U extends T
? U | `${U}${Combinations<Exclude<T, U>>}`
: never;
type AllCombinations<S extends string> = Combinations<StringToUnion<S>>;
Solution by codeisneverodd
#22206
type AllCombinations<S extends string, U = '', U1 = U> =
S extends `${infer A}${infer Rest}`
? AllCombinations<Rest, U | A>
: U extends string
? U | `${U}${AllCombinations<'', Exclude<U1, U>>}`
: ''
Solution by drylint
#22154
type ToUnion<T extends string> = T extends `${infer F}${infer R}` ? F | ToUnion<R> : never;
type AllCombinationsByTypes<T extends string, U extends string = T> = [T] extends [never] ? ''
: T extends string ? `${T | ''}${AllCombinationsByTypes<Exclude<U, T>>}` : '';
type AllCombinations<T extends string> = AllCombinationsByTypes<ToUnion<T>>
Solution by yeyunjianshi
#22014
type AllCombinations<S, Character extends string = "", CharUnion extends string = Character> =
S extends `${infer First}${infer Remainder extends string}`
? AllCombinations<Remainder, Character | First>
: Character extends "" ? "" :
`${Character}${AllCombinations<"", CharUnion extends Character ? "" : CharUnion>}`;
Solution by gaac510
#21187
// your answers
// copy
type StringToUnion<S> = S extends `${infer F}${infer R}` ? F | StringToUnion<R> : S
type AllCombinations<
S extends string,
T extends string = StringToUnion<S>,
U extends string = T,
> = S extends `${infer F}${infer R}`
? U extends U
? `${U}${AllCombinations<R, U extends '' ? T : Exclude<T, U>>}`
: never
: ''
Solution by Quanzhitong
#19818
Well, after reviewing the solution list, I found most solutions are the version or variantions of String2Union. This solution may provide a new branch of idea for us.
Simply, by just describing the algorithm, we get the anwser.
// util, get first character from an string
type Head<T extends string> = T extends `${infer First}${any}` ? First : never
// C is the current character to be handled in S
type AllCombinations<S extends string, C extends string = ''> =
S extends '' ? '' : // edge case, fast return
C extends '' // is this the first time to handle S?
? AllCombinations<S, Head<S>> // if so, we start handling it from its first character
: S extends `${infer Left}${C}${infer Right}` // else, we match S into 3 parts: Left, C, Right
// in the view of algorightm of combination, the final result is acctually the union of following parts ...
? AllCombinations<`${Left}${Right}`> // 1. the combinations of the rest characters without current character
| `${C}${AllCombinations<`${Left}${Right}`>}` // 2. the combinations of the rest characters without current character, prefixed by current character
| AllCombinations<S, Head<Right>> // 3. the combinations of the all characters, with the next character to be handled
: never
playground
Solution by zhaoyao91
#19690
// 将字符串转化为`Union`类型
type StringToUnion<S extends string> = S extends `${infer F}${infer R}`
? F | StringToUnion<R>
: "";
type Combinations<T extends string, U = T> = U extends T
? U | `${U}${Combinations<Exclude<T, U>>}`
: never;
type AllCombinations<S extends string> = Combinations<StringToUnion<S>>;
Solution by CaoXueLiang
#18249
type StringToUnion<T extends string> = T extends `${infer F}${infer R}` ? F | StringToUnion<R> : ''
type Combinations<T extends string, U = T> = U extends T
? U | `${U}${Combinations<Exclude<T, U>>}`
: never
type AllCombinations<S extends string> = Combinations<StringToUnion<S>>
Solution by milletlovemouse
#17626
type StrToUnion<S extends string> = S extends `${infer F}${infer R}` ? F | StrToUnion<R> : never;
type Pair<S extends string, T extends string = S> =
[S] extends [never]
? ''
: S extends string
? `${S}${Pair<Exclude<T, S>>}` | Pair<Exclude<T, S>>
: never
type AllCombinations<S extends string> = Pair<StrToUnion<S>>
Solution by YOUNGmaxer
#17548
Question & Answer
type AllCombinations<S extends string> = UnionToCombination<SplitToUnion<S>>
type SplitToUnion<S extends string> = S extends `${infer Head}${infer Tail}` ? Head | SplitToUnion<Tail> : never
type UnionToCombination<U extends string, Item extends string = U> = [U] extends [never]
? ''
: Item extends Item
? `${Item | ''}${UnionToCombination<Exclude<U, Item>>}`
: never
- https://github.com/type-challenges/type-challenges/issues/14833 이랑 비슷하게 풀었다.
Solution by doobee98
#16663
首先，看结果我们需要一个联合类型，那么我们可以通过分离联合类型并递归来实现。
先实现一个字符串转联合类型的工具类型 StringToUnion<S>，注意这里会返回空字符串 ''。
type StringToUnion<S> = S extends `${infer F}${infer R}` ? F | StringToUnion<R> : S
我们需要在递归中保存联合类型，因此需要添加一个参数 T，默认值为 StringToUnion<S>。我们还需要将联合类型分离，因而再添加一个参数 U，默认值为 T。
递归体内，我们需要每次将用到的 U 从 T 中删去，我们可以用 Exclude 类型：
type AllCombinations<
S extends string,
T extends string = StringToUnion<S>,
U extends string = T,
> = U extends U ? `${U}${AllCombinations<S, Exclude<T, U>>}` : never
现在这段代码无论传什么都会返回 never，因为最后联合类型 T 中的所有类型都被删去了，但我们的逻辑是正确的，现在就保持这样。
接下来我们考虑空字符串 ''，我们可以将 ''，'A'，'AB' 这样的结果视作字母与多个空字符串传的组合，换言之，空字符串在排列组合中可以出现多次。
如何做到呢？如果 U 为空字符串 ''，那么就不从 T 中将其删去，将它保留到一下次递归即可：
type AllCombinations<
S extends string,
T extends string = StringToUnion<S>,
U extends string = T,
> = U extends U ? `${U}${AllCombinations<S, U extends '' ? T : Exclude<T, U>>}` : never
最后，我们需要想想怎么让我们的的类型跳出递归。现在，由于空字符串不会被从 T 中删去，这段代码会无限递归，而且，我们也无法通过 T 来判断是否应当跳出递归。那么我们还能通过什么来判断呢？
我猜你已经想到了，那就是 S 的长度。我们可以每次递归从 S 中删去一个字符，再在递归前对其进行非空判断即可。
那么我们最终的代码为：
type StringToUnion<S> = S extends `${infer F}${infer R}` ? F | StringToUnion<R> : S
type AllCombinations<
S extends string,
T extends string = StringToUnion<S>,
U extends string = T,
> = S extends `${infer F}${infer R}`
? U extends U
? `${U}${AllCombinations<R, U extends '' ? T : Exclude<T, U>>}`
: never
: ''
Solution by Gu-Miao
#16430
// your answers
type ToUnion<S extends string = ''> = S extends `${infer R}${infer D}` ? R | ToUnion<D> : never;
type Pair<S extends string, T extends string = S> = [S] extends [never] ? '' : S extends string ? `${S}${Pair<Exclude<T, S>>}` | Pair<Exclude<T, S>> : never;
type AllCombinations<S extends string> = Pair<ToUnion<S>>
Solution by jiaaoMario
#16287
// your answers
type StringToUnion<S extends string = ''> = S extends `${infer F}${infer R}`
? F | StringToUnion<R>
: never
type Combinations<T extends string> = [T] extends [never]
? ''
: '' | { [K in T]: `${K}${Combinations<Exclude<T, K>>}` }[T]
type AllCombinations<S extends string> = Combinations<StringToUnion<S>>
Solution by humandetail
#16252
// your answers
type Permutations<
T extends string,
A extends string=T>=
[T] extends [never]
? ''
: T extends string
? `${T}${Permutations<Exclude<A,T>>}`|Permutations<Exclude<A,T>>
: never ;
type StringToUnion<
S extends string> =
S extends `${infer R}${infer U}`
? R|StringToUnion<U>
: never ;
type AllCombinations<
S extends string> =
Permutations<StringToUnion<S>> ;
Solution by justBadProgrammer
#15396