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