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
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:
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.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>
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>>] :
[]
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
type Permutation<T, K = T> = [T] extends [never] ? [] : K extends K ? [K, ...Permutation<Exclude<T, K>>] : never;
Solution by jjswifty #27473
This one was a really difficult one!
The thing is, it is conceptually quite easy. But the syntax of the conditional types in Typescript is what made it quite challenging for me. Let me explain:
type DistributiveConditionalType<UnionType> = UnionType extends any ? UnionType : never
What you are looking at above is a generic type that takes a union type (e.g. '1' | '2' | '3'
) and returns the same union type. But how does it do it?
In the answer of the conditional type (following the question mark), UnionType
DOES NO LONGER REFER to the union type as a whole but rather only one of its constituent literal types. Namely, '1'
, '2'
or '3'
. So, what happens if we want, as part of our conditional typing, to use the union type itself?
This is exactly the challenge here in my opinion. And as much as I did try to use a pseudo generic type for it equating it to the union type. I did not manage to do it in the elegant way shown in other solutions.
My solution was more lengthy which I would like to share below.
type Exclude<U, L> = U extends L ? never : U // Exclude a literal type from a union type
// This is an auxiliary generic type I introduced to solve the problem
type PermutatorCore<U, U2, T extends any[]> = // U2 here is passed the same type as U
U extends any ? // Now U becomes distributive, U2 still refers to the union type
Permutation<Exclude<U2, U>, [...T, U]> : never
type Permutation<U, T extends any[] = []> =
[U] extends [never] ? [...T] :
PermutatorCore<U, U, [...T]> // Utilise the generic type above to pass U twice as U and U2
Solution by diraneyya #26995
/* _____________ Your Code Here _____________ */
type Permutation<U, C = U> = [U] extends [never] ? [] : U extends C ? [U, ...Permutation<Exclude<C, U>>] : never;
Solution by phinixsdsd #26894
type GA<S, T = S> = S extends any ? ([T] extends [infer R] ? [S, ...(GA<Exclude<R, S>> extends never ? [] : GA<Exclude<R, S>>)] : []) : []
type Permutation<T> = GA<T> extends never ? [] : GA<T>
Solution by Acoooooooer #26783
type Permutation<T, K = T> = [T] extends [never] ? [] : K extends K ? [K, ...Permutation<Exclude<T, K>>] : never
Solution by smileboyi #26746