联合类型全排列

约 820 字大约 3 分钟

2022-12-01

题目

实现联合类型的全排列，将联合类型转换成所有可能的全排列数组的联合类型。

type perm = Permutation<'A' | 'B' | 'C'>
// ['A', 'B', 'C'] | ['A', 'C', 'B'] | ['B', 'A', 'C'] | ['B', 'C', 'A'] | ['C', 'A', 'B'] | ['C', 'B', 'A']

解题思路

这个挑战需要我们深入理解条件类型分支 Distributive Conditional Types。在我们对联合类型进行条件类型推断时：

type Permutation<T> = T extends T ? [T] : never

假设 T 为 'A' | 'B' | 'C':

type Result
 = Permutation
<'A' | 'B' | 'C'>
//

T extends T 从语法上看起来很怪，但它实际上是从泛型 T 中取出每一个成员，判断该成员是否在联合类型 T 中。

在理解了条件类型分支后，再来看联合类型的全排列，当 T 为 'A' | 'B' | 'C' 时，存在以下的所有排列：

首位成员	全部成员	去除首位成员
A	A, B, C	B, C
	A, C, B	C, B
B	B, A, C	A, C
	B, C, A	C, A
C	C, A, B	A, B
	C, B, A	B, A

观察可以发现，在首位成员确定时，全排列就是首位成员加上剩余成员的全排列的集合。

首位成员	剩余成员	全排列
A	B, C	A, B, C
	C, B	A, C, B

因此可以通过递归的方式，在 type Permutation<T> = T extends T ? [T] : never 中添加剩余成员全排列集合：

type Permutation<T, U = T> = U extends U
  ? [U, ...Permutation<Exclude<T, U>>]
  : never

这里我们使用一个泛型参数 U 保存条件类型分支中的成员。

同时，还需要考虑递归应该在何时停止，当联合类型 T 中没有成员时，即 never 时，应该终止递归。

在 typescript 中，我们不能通过 T extends never ？ true : false 判断一个类型是否为 never，因为在 T extends never 中 never 本质上是一个没有成员的联合类型，这导致了 never extends never ? true : false 整体被跳过了，得到的结果为 never , 而不是 true/false。

要避免这种情况，可以在extends 两边的类型用方括号包裹，这可以避免触发条件类型分支：

type Permutation<T, U = T> = [T] extends [never]
  ? []
  : T

答案

type Permutation<T, U = T> = [T] extends [never]
  ? []
  : U extends U
    ? [U, ...Permutation<Exclude<T, U>>]
    : never

验证

type cases
 = [
  Expect
<Equal
<Permutation
<'A'>, ['A']>>,
  Expect
<Equal
<Permutation
<'A' | 'B' | 'C'>, ['A', 'B', 'C'] | ['A', 'C', 'B'] | ['B', 'A', 'C'] | ['B', 'C', 'A'] | ['C', 'A', 'B'] | ['C', 'B', 'A']>>,
  Expect
<Equal
<Permutation
<'B' | 'A' | 'C'>, ['A', 'B', 'C'] | ['A', 'C', 'B'] | ['B', 'A', 'C'] | ['B', 'C', 'A'] | ['C', 'A', 'B'] | ['C', 'B', 'A']>>,
  Expect
<Equal
<Permutation
<boolean>, [false, true] | [true, false]>>,
  Expect
<Equal
<Permutation
<never>, []>>,
]

联合类型全排列

题目

解题思路

答案

验证

参考