Skip to content

联合类型全排列

约 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' 时,存在以下的所有排列:

首位成员全部成员去除首位成员
AA, B, CB, C
A, C, BC, B
BB, A, CA, C
B, C, AC, A
CC, A, BA, B
C, B, AB, A

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

首位成员剩余成员全排列
AB, CA, B, C
C, BA, 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 nevernever 本质上是一个没有成员的联合类型, 这导致了 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>, []>>,
]

参考