文字の組み合わせ型関数の作り方

正規表現を扱うユーティリティメソッドを作ろうとしていて、flagsに指定できる文字(`g`,`i`,`m`,`s`,`u`,`y`)を型指定で限定できないかと考えました。

でも全部の組み合わせをいちいち書いてられないので、指定した文字の全ての組み合わせを表す型関数を作ってみました。

:::note
2021/11/07改訂: 1つのtypeだけで実現できる形に書き換えました。
:::

## TL; DR

```ts
/** SETの文字の全ての組み合わせ */
type AllCombinations<SET extends string> =
  [SET] extends [never]
    ? ''
    : '' | {[FIRST in SET]: `${FIRST}${AllCombinations<Exclude<SET, FIRST>>}`}[SET];

type TEST_AllCombinations_ABCD = AllCombinations<'A' | 'B' | 'C' | 'D'>;
// -> type TEST_AllCombinations_ABCD = "" | "A" | "B" | "C" | "D" | "CD" | "DC" | "BCD" | "BDC" | "BD" | "DB" |
//    "CBD" | "CDB" | "BC" | "CB" | "DBC" | "DCB" | "ABCD" | "ABDC" | "ACBD" | "ACDB" | "ADBC" | "ADCB" | "ACD" |
//    "ADC" | ... 39 more ... | "DCBA"
type TEST_AllCombinations_ABCDEFGH = AllCombinations<'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H'>;
// -> type TEST_AllCombinations_ABCDEFGH = "" | "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "GH" | "HG" |
//    "FGH" | "FHG" | "FH" | "HF" | "GFH" | "GHF" | "FG" | "GF" | "HFG" | "HGF" | "EFGH" | "EFHG" | "EGFH" |
//    "EGHF" | "EHFG" | ... 109574 more ... | "HGFEDCBA"

declare function test(arg: AllCombinations<'A' | 'B' | 'C' | 'D'>): void;
test('AD'); // OK
test('DA'); // OK 順不同
test('ADE'); // Error 範囲外の文字は受け付けない
test('AA'); // Error 同じ文字二つは受け付けない

// 使いどころ
function re(pattern: string, flags: AllCombinations<'g' | 'i' | 'm' | 's' | 'u' | 'y'>): RegExp {
  return new RegExp(pattern, flags);
}
```

[Playground](https://www.typescriptlang.org/play?#code/PQKhAIGUFEBVDsGQgZGAJfegLRUGYM9AivofwZAQKoPEMg2gzgjABQALgJ4AOApuAIIA2rAwgPYC2ARgEsAdgEMqArkIDOAHhixwDAB5UGQgCZTwUqgCdhAcwB84ALwVw4ANryAuopVrN1oQwBuDXbYuXwAfnAAckCfSwAuIMDwAB9wAG8rADEASQAlSAVhKDhbCIADABI4lPTYAF8itk5eQVFxSVloJQBjVgBXdQY5OAAacBKMoyMyvLKbHIBuCmp6JlhoDIB9Ku5+YTEJaWWAIQ4AETMWdlXajYaZQOYo2MDt66COe8C9wKMp4GBwAFoTWkZweZLFY1db1LbMXYHUzgABEMJisOY8NiMO2yNhHHRML2WP2WL2mIRqLxRO2BKxZPxaJiFA+vgxlKJ+2pKN2uJZsL2bKJBI5MIhJJREPJROYHEZQuZWOYXMJQt50sFtM+vn5ItiADoteAAMwATnAPC4uiYWo1PPFSJm-0BsGWxxBdU2Uh2+2giQA4gAJQ7AtZO86XJ53BGBR6hl6h6BPRJPD1PL2vd6fH7gP5zBZ2v2nMEugV7d3ew5w0UU3H4rHQLGJLEerFe2sNoleus0umqz1NlGJFvVruwr01okenuNofd1sokf1z316dEwv9mHu3sLkdd5X05fe8ew6CDyfgM3gACMAAY9QBWADsABZDcbTdqUS3EtBeVaKJ1WiITeAAGZtEIzRgmmDA6AAFL+BgRNmoLOhcVyhiGNzhjcLxGAAlBEbhcAI6hTKokGXC8mETOAdIAPIANLUOBVAQc8VxkRRnw0eAgBgGYAsHKADAqdHETK0YsXS0C6LoxrgIAI96AE9qgBomvAgDhpoA6tqAPYMgDryoAigyABtyGmAFYMgAiDPxDGXMx5EiWJEk8YAGgzKYAMXKACYM6naXphmboA-vL6YAlgyAMoMgCxDBQgHAaBJoQXQYiqLoQgRDo+hCAYfT-qwIgGFIsEOv6ZzSBcBhPAITw8E8UhPG0Tw0K82HgKkDAGE0dDxD4JpUG0kXgK4ADulXVbVoXhZ4QgJUlKVkRQZQUEAA)

:::note warn
テンプレートリテラル型を使っているのでtypescript 4.1以降でないと使えません。
:::

:::note warn
テンプレートリテラル型の制限により9文字以上を指定するとエラーになります。
:::

:::note warn
指定するそれぞれの文字列に1文字でないものが含まれている場合、重複している場合は考慮していません。
:::

## 作り方

まず、1文字だけ、例えば`'A'`を使った文字列の組み合わせを考えます。

手動で書くと以下のようになります。

```ts
type AllCombinations_A = '' | 'A';
```

同様に`'B'`であれば以下のようになります。

```ts
type AllCombinations_B = '' | 'B';
```

次に、2文字、`'A'`と`'B'`を使った組み合わせを考えます。

手動では以下のようになります。

```ts
type AllCombinations_AB = '' | 'A' | 'B' | 'AB' | 'BA';
```

これをテンプレートリテラル型を使って書き換えると

```ts
type AllCombinations_AB =
  | ''
  | `A${AllCombinations_B}`
  | `B${AllCombinations_A}`;
```

つまり、最終形の`AllCombinations`が完成していると仮定するなら、以下のように書けることになります。

```ts
type AB = 'A' | 'B';
type AllCombinations_AB =
  | ''
  | `${'A'}${AllCombinations<Exclude<AB, 'A'>>}`
  | `${'B'}${AllCombinations<Exclude<AB, 'B'>>}`;
```

更にまとめるとこんな感じ。

```ts
type AllCombinations_AB = '' | {[FIRST in AB]: `${FIRST}${AllCombinations<Exclude<AB, FIRST>>}`[AB];
```

3文字、`'A'`、`'B'`、`'C'`を使った組み合わせも同様に考えてみると、以下のようになっていることが分かります。

```ts
type ABC = 'A' | 'B' | 'C';
type AllCombinations_ABC = '' | {[FIRST in ABC]: `${FIRST}${AllCombinations<Exclude<ABC, FIRST>>}`[ABC];
```

これを再帰を使って一般化して書きなおすと以下のようになります。

```ts
type AllCombinations<SET extends string> =
  '' | {[FIRST in SET]: `${FIRST}${AllCombinations<Exclude<SET, FIRST>>}`}[SET];
```

これでは再帰の終了条件がなく無限ループになってしまいエラーになるので、終了条件としてSETが空っぽになったら終わりとします。

```ts
type AllCombinations<SET extends string> =
  [SET] extends [never] ? '' :
  '' | {[FIRST in SET]: `${FIRST}${AllCombinations<Exclude<SET, FIRST>>}`}[SET];
```

※ `[SET] extends [never]` は[type challengeのIsNever](https://github.com/type-challenges/type-challenges/blob/master/questions/1042-medium-isnever/README.md)の解答から借用

実際に書いて試してみると

```ts
type TEST_AllCombinations_A = AllCombinations<'A'>;
// -> type TEST_AllCombinations_A = "" | "A"
type TEST_AllCombinations_AB = AllCombinations<'A' | 'B'>;
// -> type TEST_AllCombinations_AB = "" | "A" | "B" | "AB" | "BA"
type TEST_AllCombinations_ABC = AllCombinations<'A' | 'B' | 'C'>;
// -> type TEST_AllCombinations_ABC = "" | "A" | "B" | "C" | "BC" | "CB" | "AB" | "AC" | "ABC" | "ACB" | "CA" |
//    "BA" | "BAC" | "BCA" | "CAB" | "CBA"
type TEST_AllCombinations_ABCD = AllCombinations<'A' | 'B' | 'C' | 'D'>;
// -> type TEST_AllCombinations_ABCD = "" | "A" | "B" | "C" | "D" | "CD" | "DC" | "BCD" | "BDC" | "BD" | "DB" |
//    "CBD" | "CDB" | "BC" | "CB" | "DBC" | "DCB" | "ABCD" | "ABDC" | "ACBD" | "ACDB" | "ADBC" | "ADCB" | "ACD" |
//    "ADC" | ... 39 more ... | "DCBA"
type TEST_AllCombinations_ABCDE = AllCombinations<'A' | 'B' | 'C' | 'D' | 'E'>;
// -> type TEST_AllCombinations_ABCDE = "" | "A" | "B" | "C" | "D" | "E" | "DE" | "ED" | "CD" | "CE" | "CDE" |
//    "CED" | "EC" | "DC" | "DCE" | "DEC" | "ECD" | "EDC" | "BC" | "BD" | "BE" | "BDE" | "BED" | "BCD" | "BCE" |
//    "BCDE" | ... 299 more ... | "EDCBA"
type TEST_AllCombinations_ABCDEF = AllCombinations<'A' | 'B' | 'C' | 'D' | 'E' | 'F'>;
// -> type TEST_AllCombinations_ABCDEF = "" | "A" | "B" | "C" | "D" | "E" | "F" | "EF" | "FE" | "DE" | "DF" | 
//   "DEF" | "DFE" | "FD" | "ED" | "EDF" | "EFD" | "FDE" | "FED" | "CD" | "CE" | "CF" | "CEF" | "CFE" | "CDE" |
//    "CDF" | "CDEF" | ... 1929 more ... | "FEDCBA"
type TEST_AllCombinations_ABCDEFG = AllCombinations<'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G'>;
// -> type TEST_AllCombinations_ABCDEFG = "" | "A" | "B" | "C" | "D" | "E" | "F" | "G" | "FG" | "GF" | "EF" |
//    "EG" | "EFG" | "EGF" | "GE" | "FE" | "FEG" | "FGE" | "GEF" | "GFE" | "DE" | "DF" | "DG" | "DFG" | "DGF" |
//    "DEF" | "DEG" | ... 13672 more ... | "GFEDCBA"
type TEST_AllCombinations_ABCDEFGH = AllCombinations<'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H'>;
// -> type TEST_AllCombinations_ABCDEFGH = "" | "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "GH" | "HG" |
//    "FGH" | "FHG" | "FH" | "HF" | "GFH" | "GHF" | "FG" | "GF" | "HFG" | "HGF" | "EFGH" | "EFHG" | "EGFH" |
//    "EGHF" | "EHFG" | ... 109574 more ... | "HGFEDCBA"
```

となっており多分合ってます。

## 限界値

テンプレートリテラル型は10万とおり以上になるとエラーになります。

`AllCombinations`では自分自身をテンプレートリテラル型に指定しているので、`AllCombinations`が10万とおり以上になる組み合わせに1文字追加するとエラーとなることがわかります。

`SET`が$n$文字のとき、`AllCombinations<SET>`が何通りあるかを$A_n$とすると、
`` '' | {[FIRST in SET]: `${FIRST}${AllCombinations<Exclude<SET, FIRST>>}`}[SET] ``から
$A_n=A_{n-1}\times n+1$になります。

`SET`が0文字のときは空文字列だけなので1とおり、つまり$A_0=1$なので順に計算していくと

- $A_1=2$
- $A_2=5$
- $A_3=16$
- ...
- $A_7=13700$
- $A_8=109601$
- $A_9=986410$

となり、8文字で10万とおりを越えてしまいます。

というわけで9文字以上を指定するとエラーになります。

実は10万とおりの制限を突破する方法もあるのですが、それを突破しても再帰回数の制限がありエラーになります。

更に再帰回数の制限を少しだけ回避する方法もあるのですが、それを使っても1文字増やせるだけで、しかもその状態だとVSCodeなどのエディタがかなり重くなります。なのでこれらの限界値は突破しないようにします。