Permutation

Challenge Link

Challenge

Implement permutation type that transforms union types into the array that includes permutations of unions.

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

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

The trick here is combining two TypeScript features: the never base case and distributive conditional types.

Breaking it down

Step 1 — Base case: [T] extends [never]

When all elements have been consumed, T becomes never. But why wrap it in an array?

// ❌ Wrong — this distributes and never fires
type Bad<T> = T extends never ? [] : ...

// ✅ Correct — wrapping disables distribution, actually checks never
type Good<T> = [T] extends [never] ? [] : ...

Because never extends never distributes into nothing (the branch is unreachable), we must wrap [T] to suppress distribution.

Step 2 — Distribute over the union: K extends K

K = T is a copy of the original union. When used in K extends K ? ... : never, TypeScript distributes over each member of K. For K = 'A' | 'B' | 'C', this produces three branches:

• 'A' extends 'A' | 'B' | 'C' → ['A', ...Permutation<'B' | 'C'>]
• 'B' extends 'A' | 'B' | 'C' → ['B', ...Permutation<'A' | 'C'>]
• 'C' extends 'A' | 'B' | 'C' → ['C', ...Permutation<'A' | 'B'>]

Step 3 — Recurse with Exclude<T, K>

Each branch picks one element K and recurses on the rest using Exclude<T, K>.

Full expansion for Permutation<'A' | 'B' | 'C'>:

['A', 'B', 'C'] | ['A', 'C', 'B']
['B', 'A', 'C'] | ['B', 'C', 'A']
['C', 'A', 'B'] | ['C', 'B', 'A']

Deep Dive

Why does K extends K distribute?

TypeScript's distributive conditional types activate when:

1. The checked type is a naked type parameter (not wrapped)
2. The type parameter represents a union

K extends K looks redundant (it's always true), but its purpose is purely to trigger distribution. Each member of the union K is processed separately, giving us one branch per element — exactly the structure we need to build permutations.

The never problem

never is the identity element of union types (never | A = A). It's also the empty set — iterating over never yields nothing. This causes a subtle issue:

// T = never
type Test = never extends never ? 'yes' : 'no' 
// Result: never (not 'yes'!)
// Because distributive CT maps over 0 elements → produces never

By checking [T] extends [never], we escape distributivity and get a proper boolean-like branch.

Complexity

For a union of n members, Permutation generates n! tuples. TypeScript has recursion depth limits, so this works fine for small unions (≤ 6–7 members) but may hit limits for larger ones.

Key Takeaways

• [T] extends [never] is the canonical pattern for detecting never without distributing
• K extends K with a copy parameter is the idiom for triggering distributive behavior to iterate over union members
• Exclude<T, K> removes the chosen element from the remaining pool for the next recursion level
• TypeScript's distributive conditional types turn a single type expression into a union — that's what makes permutations expressible without any loops

中文解析

类型定义解读

type Permutation<T, K = T> =
  [T] extends [never]           // 将 T 包裹进数组，禁止分布展开，检测 T 是否为 never（递归终止条件）
    ? []                        // T 已耗尽 → 返回空元组
    : K extends K               // K 是 T 的副本，这里触发分布式条件类型，对联合的每个成员单独处理
      ? [K, ...Permutation<Exclude<T, K>>]  // 选取当前成员 K，递归处理剩余 Exclude<T,K>
      : never

逐步分析

为什么需要两个类型参数 T 和 K？

• T 是"剩余可选元素池"，每次递归都通过 Exclude<T, K> 缩小
• K = T 是当前层级的"备用副本"，用于触发分布，且值等于 T

如果只用 T 一个参数，T extends T 在递归时会把已缩小的 T 再次分布，但我们在递归调用中传递的是缩小后的值，所以实际上 K = T 的默认值让一切自洽。

关键技巧 1：[T] extends [never]——检测 never 的标准写法

// ❌ 错误写法
type Check<T> = T extends never ? 'yes' : 'no'
// 当 T = never 时，分布式展开产生 0 个分支，结果是 never（不是 'yes'）

// ✅ 正确写法  
type Check<T> = [T] extends [never] ? 'yes' : 'no'
// 包裹后禁止分布，[never] extends [never] 正常求值为 true

关键技巧 2：K extends K——利用"永真条件"触发分布

K extends K 对任意类型 K 都为真，但它的作用不是过滤，而是触发分布式条件类型。
当 K = 'A' | 'B' | 'C' 时，TypeScript 将其展开为：

| ('A' extends 'A'|'B'|'C' → ['A', ...Permutation<'B'|'C'>])
| ('B' extends 'A'|'B'|'C' → ['B', ...Permutation<'A'|'C'>])
| ('C' extends 'A'|'B'|'C' → ['C', ...Permutation<'A'|'B'>])

最终得到 3! = 6 个元组的联合类型。

完整递归展开（以 'A'|'B'|'C' 为例）

Permutation<'A'|'B'|'C'>
├─ K='A': ['A', ...Permutation<'B'|'C'>]
│          ├─ K='B': ['A','B', ...Permutation<'C'>] → ['A','B','C']
│          └─ K='C': ['A','C', ...Permutation<'B'>] → ['A','C','B']
├─ K='B': ['B', ...Permutation<'A'|'C'>] → ['B','A','C'] | ['B','C','A']
└─ K='C': ['C', ...Permutation<'A'|'B'>] → ['C','A','B'] | ['C','B','A']

考察知识点

• 分布式条件类型（Distributive Conditional Types）：当条件类型的检测对象是"裸类型参数"时，对联合类型的每个成员分别求值，结果再合并为联合类型
• [T] extends [never] 模式：包裹元组是禁止分布展开的标准手段，专门用于正确检测 never
• K extends K 分布触发技巧：用"永真条件"纯粹为了触发分布，而非过滤——这是生成联合的"发动机"
• Exclude<T, K>：从联合类型中去掉某个成员，配合递归实现"已选元素不再参与后续选择"
• 默认类型参数：K = T 让调用者只需传一个参数，内部通过副本保持逻辑清晰
• 递归复杂度：n 个成员的联合 → n! 个元组，TypeScript 递归深度有限，实际使用 ≤ 7 个成员