FE/type-challenge

21220. PermutationsOfTuple

최토피 2023. 10. 11. 12:07
728x90

문제

Given a generic tuple type T extends unknown[], write a type which produces all permutations of T as a union.

PermutationsOfTuple<[1, number, unknown]>
/**
 * Should return:
 * | [1, number, unknown]
 * | [1, unknown, number]
 * | [number, 1, unknown]
 * | [unknown, 1, number]
 * | [number, unknown, 1]
 * | [unknown, number ,1]
 */

cases

type cases = [
  Expect<Equal<PermutationsOfTuple<[]>, []>>,
  Expect<Equal<PermutationsOfTuple<[any]>, [any]>>,
  Expect<Equal<PermutationsOfTuple<[any, unknown]>, [any, unknown] | [unknown, any]>>,
  Expect<Equal<
    PermutationsOfTuple<[any, unknown, never]>,
    | [any, unknown, never]
    | [unknown, any, never]
    | [unknown, never, any]
    | [any, never, unknown]
    | [never, any, unknown]
    | [never, unknown, any]
  >>,
  Expect<Equal<
    PermutationsOfTuple<[1, number, unknown]>,
    | [1, number, unknown]
    | [1, unknown, number]
    | [number, 1, unknown]
    | [unknown, 1, number]
    | [number, unknown, 1]
    | [unknown, number, 1]
  >>,
  ExpectFalse<Equal<PermutationsOfTuple<[ 1, number, unknown ]>, [unknown]>>,
]

문제 링크

정답

type PermutationsOfTuple<T extends unknown[], R extends unknown[] = []> = T extends [infer T1, ...infer Rest]
  ? PermutationsOfTuple<Rest, Permutations<T1, R>>
  : R

type Permutations<T, A extends unknown[], P extends unknown[] = []> =
    A['length'] extends P['length']
      ? [...A, T]
      : PutAt<T, A, P['length']> | Permutations<T, A, [...P, unknown]>

type PutAt<T, A extends unknown[], P extends number, Prev extends unknown[] = []> =
    P extends Prev['length'] ? [...Prev, T, ...A] : A extends [infer A1, ...infer Rest]
      ? PutAt<T, Rest, P, [...Prev, A1]>
      : never

풀이

조건

  1. T의 모든 요소를 사용하여 순열을 구한다.

해설

앞의 요소부터 차례로 순열을 구하는 타입 PermutationsOfTuple을 생성한다.

type PermutationsOfTuple<T extends unknown[], R extends unknown[] = []> = T extends [infer T1, ...infer Rest]
  ? PermutationsOfTuple<Rest, Permutations<T1, R>>
  : R

위 타입은 재귀적으로 모든 요소를 돌아 마지막에 저장된 R을 리턴하는 타입이다.

기존에 계산된 순열에 요소를 추가해서 새로운 순열을 생성하는 Permutations타입을 추가한다.

type Permutations<T, A extends unknown[], P extends unknown[] = []> =
    A['length'] extends P['length']
      ? [...A, T]
      : PutAt<T, A, P['length']> | Permutations<T, A, [...P, unknown]>

이 타입은 튜플 각 요소의 사이사이에 PutAt를 이용하여 새로운 요소를 추가한다.

PutAt는 튜플의 원하는 위치에 새로운 요소를 추가하는 타입이다. 다음과 같이 정의할 수 있다.

type PutAt<T, A extends unknown[], P extends number, Prev extends unknown[] = []> =
    P extends Prev['length'] ? [...Prev, T, ...A] : A extends [infer A1, ...infer Rest]
      ? PutAt<T, Rest, P, [...Prev, A1]>
      : never

 

혹시 오류나 개선점이 있다면 댓글 부탁드립니다.

728x90