Завдання

Реалізуйте тип Permutation<U>, який перетворює об’єднання в масив, що включає перестановки елементів.

type perm = Permutation<"A" | "B" | "C">;
// expected ['A', 'B', 'C'] | ['A', 'C', 'B'] | ['B', 'A', 'C'] | ['B', 'C', 'A'] | ['C', 'A', 'B'] | ['C', 'B', 'A']

Розв’язок

Одне з найулюбленіших завдань. На перший погляд, складне завдання, але це не так. Щоб зрозуміти рішення, я розповім вам про алгоритм “розділяй і володарюй”

Якщо завдання дуже складне, то розділи його на менші/простіші завдання. Замість того щоб шукати перестановки в усіх елементах, почнемо з проблеми, де вони відсутні або є тільки один елемент.

У випадку, коли T без елементів, ми повертаємо порожній масив. Тобто коли немає елементів – немає перестановок. В іншому випадку, коли T містить один елемент, то перестановка одного елемента буде цей самий (один) елемент. Виразимо це використовуючи умовні типи:

type Permutation<T> = T extends never ? [] : [T];

Це рішення навіть проходить один тест. Тест, який перевіряє перестановки одного елементу. Все як і планували.

Але як ми знайдемо перестановки двох елементів? Алгоритм “розділяй і володарюй” все ще актуальний. Наприклад, щоб дізнатись Permutation<‘A’ | ‘B’>, треба взяти перший елемент A та знайдемо перестановки по решті елементів, тобто Permutation<‘B’>. Повторюємо для наступного елементу. Беремо елемент B та шукаємо перестановки по решті об’єднань Permutation<‘A’>. Ми вже знаємо як це робити.

Permutation<‘A’ | ‘B’> -> [‘A’, ...Permutation<‘B’>] + [‘B’, ...Permutation<‘A’>] -> [‘A’, ‘B’] + [‘B’, ‘A’]

Не важливо наскільки глибоко ми пірнемо рекурсивно, рано чи пізно ми дійдемо до базового випадку рекурсії – один елемент в об’єднанні.

Змоделюємо таку поведінку на рівні системи типів. Умовні типи в TypeScript дистрибутивні для об’єднань. Коли ми пишемо T extends Some<T>, де T це об’єднання, TypeScript бере кожен елемент з об’єднання та застосовує до нього умовний тип. Використаємо це для того, щоб перебрати всі елементи об’єднання за допомогою конструкції T extends infer U ? U : never, таким чином ми будемо знати які елементи виключити з рекурсії.

Знаючи, які елементи потрібно виключити, ми можемо реалізувати алгоритм “розділяй і володарюй”, замінивши [T].

type Permutation<T> = T extends never
  ? []
  : T extends infer U
  ? [U, ...Permutation<Exclude<T, U>>]
  : [];

Ми близькі до рішення. Теоретично все має працювати, та, на жаль, не працює. Що пішло не так? Ми отримуємо never замість перестановок. Після деяких роздумів, я зрозумів, що треба огорнути наш умовний тип T у масив:

type Permutation<T> = [T] extends [never]
  ? []
  : T extends infer U
  ? [U, ...Permutation<Exclude<T, U>>]
  : [];

Якщо чесно, я так і не зрозумів в чому була проблема. В нашому випадку вираз T extends infer U, працює не так, як я очікував. Я був дуже здивований, коли просте копіювання параметра типу T в інший розв’язує проблему:

type Permutation<T, C = T> = [T] extends [never]
  ? []
  : C extends infer U
  ? [U, ...Permutation<Exclude<T, U>>]
  : [];

Посилання