permutation https://github.com/type-challenges/type-challenges/blob/master/questions/296-medium-permutation/README.md

permutation.ts

// TypeScript Version 4.3.5

// 原问题链接:
// https://github.com/type-challenges/type-challenges/blob/master/questions/296-medium-permutation/README.md

// 下面是思考过程:


// 这个问题本质是如何穷举出形如 [1, 2, 3] 的所有组合, 那么如何告诉机器如何穷举呢 ?

// 思考观察:
// 第零种情况: [] 的所有组合是 []
// 第一种情况: [1] 的所有组合是 [1]
// 第二种情况: [1, 2] 的所有组合是 [1, 2] | [2, 1]
// 第三种情况: [1, 2, 3] 的所有组合是 [1, 2, 3] | [2, 1, 3] | [2, 3, 1] | [1, 3, 2] | [3, 1, 2] | [3, 2, 1]

// 观察到第二和第三种情况，很显然:
// 其实第三种其实是将 3 分别插入到 ([1,2] | [2,1]) 里面的不同下标而已
// 即所谓 3 ==插入=> ([1,2] | [2,1]) 就是:
// [3,1,2] | [1,3,2] | [1,2,3]    (3 塞在 0 1 2 三个坐标里面)
// [3,2,1] | [2,3,1] | [2,1,3]


// 因此, 总结出递推关系:
// 第 n+1 种情况是 N ==插入=> (第 n 种情况) 
// ....
// 第二种情况是 2 ==插入=> [1] 即为 [2,1] | [1,2]
// 第一种情况是 1 ==插入=> []  即为 [1]
// 第 0 种情况是 void ==插入=>[] 即为 []

// ... 也就是说, 欲求 n 项, 则必求 n - 1 项, 直到第零项

// 所以首先我们得实现 "将单个元素插入分别到 tuple 的不同下标中" 这件事, 即下面的 Insert<E, A>
// 然后根据 Insert<E, A> 实现递推关系 最终求解

// 将 E 插入到 A 中有多少种结果, 具体见后面的 I1 和 I2
type Insert<E, A> = (
  A extends [infer One, ...infer Rest]
    ? (
      [E, One, ...Rest] |
      [One, E, ...Rest] |
      [One, ...Insert<E, Rest>] |
      [One, ...Rest, E]
    )
    : [E] // 即 Insert<E, []>
);

// GG 插入到 [2, 3]
type I1 = Insert<'GG', [2, 3]>;
// GG 插入到 [1, 2, 3]
type I2 = Insert<'GG', [1, 2, 3]>;

// 然后, 利用 Insert<E, A> 表达出递推关系
// 穷举 Tuple 的所有排列
// [1, 2, 3] ==> 6 种排列
// [1, 2, 3] | [2, 1, 3] | [2, 3, 1] | [1, 3, 2] | [3, 1, 2] | [3, 2, 1]
type TupleSet<A> = (
  A extends [infer One, ...infer Rest]
    ? Insert<One, TupleSet<Rest>>
    : []
);


type R0 = TupleSet<[]>;
type R1 = TupleSet<[1]>;
type R2 = TupleSet<[1, 2]>;
type R3 = TupleSet<[1, 2, 3]>;
type R4 = TupleSet<[1, 2, 3, 4]>;


// ["A", "B", "C"] |
// ["B", "A", "C"] |
// ["B", "C", "A"] |
// ["A", "C", "B"] |
// ["C", "A", "B"] |
// ["C", "B", "A"]
type ABCSet = TupleSet<['A', 'B', 'C']>;


// 最后我们吧 union 1|2|3 转为 [1,2,3] 这个网上有方案, 具体原理嗨鸡儿麻烦
// 网上抄的 UnionToTuple: (1 | 2) ==> [1, 2]
// https://stackoverflow.com/questions/55127004/how-to-transform-union-type-to-tuple-type
type UnionToIntersection<U> = (
  (U extends any ? (k: U) => void : never) extends ((k: infer I) => void) ? I : never
);
type LastOf<T> = (
  UnionToIntersection<T extends any ? () => T : never> extends () => (infer R) ? R : never
);
type Push<T extends any[], V> = [...T, V];
type TuplifyUnion<T, L = LastOf<T>, N = [T] extends [never] ? true : false> = (
  true extends N ? [] : Push<TuplifyUnion<Exclude<T, L>>, L>
);



// 最终可以得到问题里面要的 Permutation<U>
type Permutation<U> = TupleSet<TuplifyUnion<U>>;


// Permutation 测试用例

// type P1 = [1, 2, 3] | [2, 1, 3] | [2, 3, 1] | [1, 3, 2] | [3, 1, 2] | [3, 2, 1]
type P1 = Permutation<1 | 2 | 3>;

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

// type P3 = [1, 2] | [2, 1]
type P3 = Permutation<1 | 1 | 1 | 2 | 2 | 2>;