mosya

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>
>}`;

まず、UAの場合は、以下のように色が展開されます。

`${"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から始まる組み合わせ

この処理が、BC""に対しても同様に行われます。

`${"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。

ReactやTypeScriptなどの周辺技術が学べる
オンライン学習サービスを作りました!

詳しくはこちら
mosya

mosyaはオンラインでHTML,CSS,JavaScriptを基本から学習できるサービスです。現役エンジニアが作成した豊富なカリキュラムに沿って学習を進めましょう。

© 2023 - mosya. All rights reserved.