Type Challenges: 00296-medium-permutation Solution

// 有一点 triky, 不过只要搞清楚判断 never 的正确方法就好了. 又是一个与 Distributive Conditional Types 相关的问题
type IsNever<T> = [T] extends [never] ? true : false
type Permutation<T, S = T> = [T] extends [never] ? [] : T extends any ? [T, ...Permutation<Exclude<S, T>>] : []

// 三种错误判断 never 的方法
type T1<T> = T extends never ? true : false
type T2<T> = [T] extends never ? true : false
type T3<T> = T extends [never] ? true : false
type r = [T1<never>, T2<never>, T3<never>]
type _ = Expect<Equal<r, [never, false, never]>>

简单来说, 当判断 A extends B 时, 会把 A 中的每个成员类型拿出来与 B 中每个成员类型匹配, 而由于 never 实际上是空集, 所以无法从中拿出任何元素用来匹配, 因此 A=never 时根本不会进行匹配, 直接返回 never; B=never 时任何匹配都失败, 得到 false.

而当加上方括号后, 编译器不会进行这个取成员类型的操作, 而是直接将此集合视为单个类型进行匹配, 所以能进行比较.

另外, S 的引入是为了保留原始 union 类型, 这样在递归参数处进行 Exclude<S, T> 时, T 是已在 extends 中被拆分的子类型, S 是原始 union 类型, 因此可以得到差集

Solution by freesrz93 #36450

explain

type U<T> = T extends 'A' ? true : nerver
type R = U<'A' | 'B' | 'C'>; // true | nerver | never -> true

When a Union Type appears on the left side of extends, ts will verify each Union Type separately and comine each result before returning.

So first judge, you cannot use T extends never, second judge, you should use K extends K

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

Solution by vaclock #35759

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

Solution by gangnamssal #35578

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

Solution by RanungPark #35516

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

Solution by HrOkiG2 #35326

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

Solution by eunsukimme #35205

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

Solution by devshinthant #34579

type Permutation<T, K=T> = [T] extends [never] ? [] : K extends infer R ? [R, ...Permutation<Exclude<T, R>>] : never

Solution by ouzexi #34006

// Algorithm
function permute(arr: number[]): number[][] {
  var result : number[][] = []
  function dfs(a: number[]) {
    if (a.length === arr.length) {
      result.push(a)
    } else {
      for (const n of arr) {
        if (a.includes(n)) {
          continue
        }
        dfs([...a, n])
      }
    }
  }
  dfs([])
  return result
}

// Type
type Permutation<T, K=T> =
[T] extends [never]
  ? [] // 空元素空排列，递归出口
  : K extends infer U // 遍历T
    ? [U, ...Permutation<Exclude<T, U>>] // 递归得到除了U以外元素的排列
    : never // never happened

// Permutation<A | B | C>
// =>
// [A, ...Permutation<B | C>]
// [A, ...[B, ...Permutation<C>]] [A, ...[C, ...Permutation<B>]]
// [A, ...[B, ...[C, []]]]] [A, ...[C, ...[B, []]]]]
// [A, B, C] [A, C, B]

// [B, ...Permutation<A | C>] 
// [B, ...[A, ...Permutation<C>]] [B, ...[C, ...Permutation<A>]]
// [B, ...[A, ...[C, []]]]] [B, ...[C, ...[A, []]]]]
// [B, A, C] [B, C, A]

// [C, ...Permutation<A | B>]
// [C, ...[A, ...Permutation<B>]] [C, ...[B, ...Permutation<A>]]
// [C, ...[A, ...[B, []]]]] [C, ...[B, ...[A, []]]]]
// [C, A, B] [C, B, A]

Solution by ScriptBloom #33909

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

Solution by chihiro365yb #33857

Unlike the most upvoted answer, I don't want to use K extends K in the second loop (because it feels somewhat counterintuitive). For the permutation solution, it's natural to iterate over T itself. Therefore, I present the following solution (which has the same effect as K extends K).

----- Above is the translation from Chinese by ChatGPT XD -----

和票数最多的答案不同，二层循环我不想使用 K extends K（因为它有点反直觉），对于 permutation 解法，我们很自然地想到对 T 本身做遍历，因此我给出如下的解法（实际效果和 K extends K 相同）

// your answers
type Permutation<T extends string | number | symbol, A extends any[] = []> = [
  T
] extends [never]
  ? A
  : { [key in T]: Permutation<Exclude<T, key>, [...A, key]> }[T];

Solution by pfan8 #33831

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

Solution by bananana0118 #32784

// It's copy+paste, but I understand the logic after wasting 30 minutes of my life.
type Permutation<T, K = T> =
    [T] extends [never]
      ? []
      : K extends K
        ? [K, ...Permutation<Exclude<T, K>>]
        : never

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

Solution by ZhulinskiiDanil #32683

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

유니언 타입이 배열의 원소로 들어가면 각각의 유니언 타입에 맞게 여러 유니언 타입이 만들어지는 것을 배웠다.
Exclude<T, K> 부분에서 K가 유니언에서 한가지로 정해진 구체적인 타입으로서 활용 가능하다는 것을 배웠다.

Solution by dev-hobin #32401

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

Solution by kai-phan #31639

// your answers
type Permutation<T, K = T> = [T] extends [never]
  ? []
  : K extends K
  ? [K, ...Permutation<Exclude<T, K>>]
  : never;

Solution by AhmedRagabKamal #31511

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

Solution by jbalancer #31173

// 你的答案
type Permutation<T, K = T> =
  [T] extends [never]
    ? []
    : T extends T
      ? [T, ...Permutation<Exclude<K, T>>]
      : never;

Solution by d1zzzzy #31145

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

Solution by kai-phan #30348

递归➕剔除

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

Solution by 1587315093 #29930

type Possible = string | number | bigint | boolean | null | undefined

type Permutation<T, K extends Array<unknown> = []> = {
  [P in T as P extends Possible ? `${P}` : never]: Exclude<T, P> extends never ? [...K, P] : Permutation<Exclude<T, P>, [...K, P]>
} extends Record<any, infer U>
  ? U extends {}
    ? U
    : []
  : never

Solution by agus-wesly #29789

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

Solution by MohammadArasteh #29409

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

Notes:

When comparing a union type to never in generic types, the result of T extends never (when T is never) would always be never because there is no member in the union can be distrubted over. Hence, use straight brackets on both sides of extends to escape the distributive behavior.
The second param K in Permutation is to reserve the original union type so we can use Exclude on it against the distrubuted member T in Exclude<K, T>
An example of how Permutation works:

// example
Permutation<'A' | 'B' | 'C'>

// step 1
['A', ...Permutation<'B' | 'C'>] | 
['B', ...Permutation<'A' | 'C'>] | 
['C', ...Permutation<'A' | 'B'>]

// step 2, in a recursive call, computing the second item in the above arraies
['B', ...Permutation<'C'>] | 
['C', ...Permutation<'B'>] |
// ...omiting the rest for ['B', ...Permutation<'A' | 'C'>] | ['C', ...Permutation<'A' | 'B'>]

// step 3
['C' | ...Permutation<never>] | 
['B' | ...Permutation<never>] |
// ...omiting the rest 

// step 4
['A', 'B', 'C'] |
['A', 'C', 'B'] |
// ...omiting the rest

Solution by qianzhong516 #28941

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

Solution by kai-phan #28838

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

Solution by hajeonghun #28825

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

Solution by DoubleWoodLin #28614

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

Solution by de-novo #28556

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

Solution by flt3150sk #28540

type Permutation<Union, Item=Union> =
  [Union] extends [never] ? [] :
    Item extends Item ?
    [Item, ...Permutation<Exclude<Union, Item>>] :
  []

thanks to help 🙏

Solution by maximallain #28343

type IsBooleanExact<T> = boolean extends T ? true : false;
type IsNever<T> = [T] extends [never] ? true : false;

type Permutation<T, K = T> = 
  IsBooleanExact<T> extends true 
    ? [false, true] | [true, false] 
    : IsNever<T> extends true 
      ? [] 
      : T extends unknown
        ? [T, ...Permutation<Exclude<K, T>>]
        : never;

Solution by viktor-sakhno-saritasa #27671