296-实现全排列

题目描述

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

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

分析

这一题可以说是典中典了，笔者第一次看到的时候，目瞪口呆，完全没有思路，只感觉难度陡然飙升。

不过现在回过头来看，这题真的是经典。

从入参来看，是一个联合类型，那么不免想到联合类型的分发特性（不了解分发特性的可以参考 实现 Exclude）。

所谓全排列，人工实现的话，也就是从 元组中挑一个出来，然后再从剩余的元素中挑一个出来，然后再从剩余的元素中挑一个出来，直到没有，就组成了其中一条排列。也就是以前学校学习排列组合学习的 A32。这个算法用 js 实现起来都有点麻烦，但是 ts 由于其分发特性，反而会更简单，但是会比较绕。

先上第一阶段的代码（不对，但是适合用于解释）：

type Permutation<T, C = T> = T extends any
  ? [T, ...Permutation<Exclude<C, T>>]
  : never;

这里确实比较绕，我尽量讲清楚：

首先是 T extends any，这里其实 写any也行，写 T 也行，因为这里只是为了触发联合类型的分发特性，要注意的是，一旦分发之后，T 表示的就是当前的元素，而非整个元组。

但是为了得到全排列，我们需要从整个元组中，排除当前的元素，所以需要再多一个参数 C = T，因为分发后，T 表示的是当前元素，所以 Exclude<C, T> 就是排除了元组中 T 元素的剩余元素，再次递归即可。罗列成步骤如下：

type Permutation<T, C = T> = T extends any
  ? [T, ...Permutation<Exclude<C, T>>]
  : never;

// step1: T extends any ? 触发分发特性
// 第一个元素： ['A', ...Permutation<Exclude<'A' | 'B' | 'C', 'A'>>]
// 嵌套：Permutation<Exclude<'A' | 'B' | 'C', 'A'>>
// T = 'B' | 'C', T extends any ? 触发分发特性
// 第一个元素 ['B', ...Permutation<Exclude<'B' | 'C', 'B'>>]
// 嵌套: Permutation<Exclude<'B' | 'C', 'B'>>
// T = 'C', T extends any，此时只有一个元素，不再分发
// ['C', ...Permutation<Exclude<'C', 'C'>>]
// 此时 Exclude<'C', 'C'> 是 never，从而导致 整个元组被归为 never
// type Case1 = [1, ...Exclude<'a', 'a'>] // never
type t = Permutation<'A' | 'B' | 'C'>;

上面注释中，解释了第一层的循环嵌套，也提到了本解法不正确的原因： type Case1 = [1, ...Exclude<'a', 'a'>] 的结果是 never，最终上述解法输出的就是 never，结果是不正确的。至于为什么，这里我也不太清楚，我们只需要针对 never 进行特殊处理即可，整理后的题解如下：

题解

type Permutation<T, C = T> =
  //  递归到最后一层时，Exclude<A, A> 会返回 never，如果是 never ，就返回空元组，这样 [1, ...[]] 就是[1]，从而还原原本的排列
  [T] extends [never]
    ? []
    : // 触发分发特性
    T extends any
    ? // 此时的 T 就是当前元素而非整个元组，故通过 C = T 保留原来的元组，从而 Exclude<C, T> 可以得到剩余元素
      [T, ...Permutation<Exclude<C, T>>]
    : never;

核心就在于分发特性后， T 表示的仅仅是当前元素，故需要 C = T 来保留原来的元组。

另一方面也是 never 的判断，这里将在 1042-isNever 一题中做详细介绍。

知识点

1. 分发特性的经典利用
2. 递归处理嵌套问题
3. never 判断