Skip to content

Instantly share code, notes, and snippets.

@dfoverdx
Last active February 7, 2023 14:20
Show Gist options
  • Save dfoverdx/8a044df48f6fa71a75caa2e6c56bd5b0 to your computer and use it in GitHub Desktop.
Save dfoverdx/8a044df48f6fa71a75caa2e6c56bd5b0 to your computer and use it in GitHub Desktop.
TypeScript Permutations Type
/**
* @document Permutations.ts
*
* I wanted to figure out, just for the challenge of it, whether I could, given an array type `A`, produce a type that
* matches any array with every element of `A` exactly once in any order. I *love* abusing the TS typing engine. It
* insulted my mother once.
*/
/**
* Returns an array type that includes every element of `T` exactly once in any order.
*
* Obviously this produces an `n!` number of matching arrays. My computer took a few minutes to verify 9-length arrays.
*/
type Permutations<T extends readonly unknown[]> =
T['length'] extends 0 | 1
? T // if T only has one permutation, just return it
: {
// put each member of T first in an array, and concatenate the permutations of T without that member
[K in keyof T & number]: [T[K], ...Permutations<ExcludeElement<T, T[K]>>]
}[keyof T & number]; // get the union of all permutations starting with each element of T
/** Removes the first instance of `T` from `A`. */
type ExcludeElement<A extends readonly any[], T extends any> =
A extends readonly [infer H, ...infer R]
? H extends T ? T extends H
? R // we've found T; just return what's left
: [H, ...ExcludeElement<R, T>] : [H, ...ExcludeElement<R, T>] // H is not our T
: A;
type A = [1, 2, 3, 4, 5, 6, 7, 8, 9];
type X = Permutations<A>;
const x: X = [5, 1, 4, 2, 3, 6, 7, 9, 8];
@ScorpioneOrzion
Copy link

ScorpioneOrzion commented Feb 7, 2023

Tested this, and removing "& number" on line 19 gives the correct result

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment