mosya<TC> - AllCombinations型を実装して、与えられた文字列のすべての組み合わせを返そうの解説
この記事はmosya<TC>の問題の一つであるAllCombinations型の解説になります。
問題
指定された文字列に含まれる文字をそれぞれ最大で1度だけ使った文字列のすべての組み合わせの型AllCombinationsを実装します。
例えば
type AllCombinations_ABC =
AllCombinations<"ABC">;
// should be '' | 'A' | 'B' | 'C' | 'AB' | 'AC' | 'BA' | 'BC' | 'CA' | 'CB' | 'ABC' | 'ACB' | 'BAC' | 'BCA' | 'CAB' | 'CBA'
解答例
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
: "";
文字列をユニオン型に変換するStringToUnionを作成
まず、文字列をユニオン型に変換するStringToUnionを作成します。
type StringToUnion<S> =
S extends `${infer F}${infer R}`
? F | StringToUnion<R>
: S;
この型は、与えられた文字列を、先頭の文字Fと残りの文字列Rに分割します。
もし分割に成功した場合は、それ以外の文字列Rに対して再帰的にこの型を適用します。
これを繰り返すことで、文字列をユニオン型に変換することができます。
AllCombinationsを作成
次に、AllCombinationsを作成します。
文字列Sを先頭の文字Fと残りの文字列Rに分割します。
S extends `${infer F}${infer R}`次に、U extends Uという条件を使い、ユニオン型のUの要素を一つずつ取り出し、再帰的に処理を適用します。
U extends U
? `${U}${AllCombinations<R, U extends '' ? T : Exclude<T, U>>}`
: never例えば、Uが"A" | "B" | "C" | ""の場合、"A"、"B"、"C"、""に対して、以下の処理が行われます。
`${U}${AllCombinations<
R,
U extends "" ? T : Exclude<T, U>
>}`;
まず、UがAの場合は、以下のように色が展開されます。
`${"A"}${AllCombinations<
R,
"A" extends ""
? "A" | "B" | "C" | ""
: Exclude<"A" | "B" | "C" | "", "A">
>}`;
文字列の先頭にAという文字が追加され、残りの文字列に対して再帰的に処理が行われます。
`${"A"}${AllCombinations<
R,
"B" | "C" | ""
>}`;
これが、文字列の長さが0になるまで繰り返されます。
`${"A"}${AllCombinations<
R,
"B" | "C" | ""
>}``${"A"}${`${"B"}${AllCombinations<
R,
"C" | ""
>}`}``${"A"}${`${"B"}${`${"C"}${AllCombinations<
R,
""
>}`}`}`;
最後に、文字列の長さが0になった場合は、空文字列を返します。
`${"A"}${`${"B"}${`${"C"}${""}`}`}`;
// 他のAから始まる組み合わせ
この処理が、BやC、""に対しても同様に行われます。
`${"B"}${AllCombinations<
R,
"A" | "C" | ""
>}``${"B"}${`${"A"}${AllCombinations<
R,
"C" | ""
>}`}``${"B"}${`${"A"}${`${"C"}${AllCombinations<
R,
""
>}`}`}`;
// 他のBから始まる組み合わせ
`${"C"}${AllCombinations<
R,
"A" | "B" | ""
>}``${"C"}${`${"A"}${AllCombinations<
R,
"B" | ""
>}`}``${"C"}${`${"A"}${`${"B"}${AllCombinations<
R,
""
>}`}`}`;
// 他のCから始まる組み合わせ
Authored by
Godai@steelydylan
Webサービスを作るのが好きなWebエンジニア。子供が産まれたことをきっかけに独立し法人化。サービス開発が大好き。
好きな言語はTypeScript。
Related
