第27關：Permutation！TypeScript 黑板上排列組合：你捨得解開嗎？

16th鐵人賽

wayz

2024-10-11 23:57:16

32 瀏覽

分享至

第27關：Permutation！TypeScript 黑板上排列組合：你捨得解開嗎？

第27關：Permutation

關卡簡介

Implement permutation type that transforms union types into the array that includes permutations of unions.

實驗一個排列類型 (permutation type)，把聯合類型 (union types) 變成一個數組 (array)，裡面包含所有可能的排列組合 (permutations)。

任務說明：

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

接下來，你的任務是讓下面的type cases測試通過：

type cases = [
  Expect<Equal<Permutation<'A'>, ['A']>>,
  Expect<Equal<Permutation<'A' | 'B' | 'C'>, ['A', 'B', 'C'] | ['A', 'C', 'B'] | ['B', 'A', 'C'] | ['B', 'C', 'A'] | ['C', 'A', 'B'] | ['C', 'B', 'A']>>,
  Expect<Equal<Permutation<'B' | 'A' | 'C'>, ['A', 'B', 'C'] | ['A', 'C', 'B'] | ['B', 'A', 'C'] | ['B', 'C', 'A'] | ['C', 'A', 'B'] | ['C', 'B', 'A']>>,
  Expect<Equal<Permutation<boolean>, [false, true] | [true, false]>>,
  Expect<Equal<Permutation<never>, []>>,
]

冒險指南：

從以下幾個方向來思考：

聯合類型 (Union Types): 在 TypeScript 中，聯合類型（例如 'A' | 'B' | 'C'）表示一個值可以是 'A'、'B' 或 'C' 其中之一。排列的任務就是從聯合類型中提取不同順序的組合。
遞迴解法 (Recursive Approach): 我們需要從聯合類型中每次取出一個元素，然後對剩下的元素進行遞迴排列。
條件型別 (Conditional Types): 條件型別是 TypeScript 用來根據不同條件決定結果類型的功能。在這裡，我們使用它來檢查聯合類型是否已經排列完畢。
Exclude 工具類型 (Exclude Utility Type): Exclude<T, U> 是 TypeScript 的內建工具類型，它可以從聯合類型 T 中排除 U 的部分。例如，Exclude<'A' | 'B' | 'C', 'A'> 會返回 'B' | 'C'。

通關方式：

解法:


type Permutation<T, K=T> =
    [T] extends [never]
      ? []
      : K extends K
        ? [K, ...Permutation<Exclude<T, K>>]
  : never

細節分析：

類型定義 (Type Definition)
type Permutation<T, K=T>:
我們定義了一個 Permutation 的類型，這個類型有兩個參數：T 和 K。
T 是我們希望生成排列的聯合類型。
K 參數默認為 T，用來在遞迴過程中代表當前處理的元素。這意味著在初始調用時，K 會與 T 相同，但隨著遞迴的進行，它會逐漸變為 T 中的具體成員。
基礎情況檢查 (Base Case Check)
[T] extends [never]:
這是一個條件型別，用來檢查 T 是否為 never 類型。
為什麼要這樣寫？: 如果 T 為 never，表示已經沒有可供排列的元素了。此時返回一個空數組 [] 作為排列的結束情況，這是遞迴的基礎情況（base case）。這行代碼確保當沒有元素時，排列將停止，並且能正確返回空數組。
遞迴情況 (Recursive Case)
K extends K:
這一行利用 TypeScript 的分配性（distributive）特性。當我們在條件型別中使用 K 時，TypeScript 會自動將 K 的每個成員提取出來進行處理。
為什麼要這樣寫？: 這使得對於聯合類型的每一個成員，我們都可以進行迭代，並且為每個成員生成其排列。
主遞迴邏輯 (Main Recursive Logic)
[K, ...Permutation<Exclude<T, K>>]:
這一行是遞迴的核心邏輯：
- K: 這是當前正在處理的元素，將它放在結果的最前面。
- ...Permutation<Exclude<T, K>>:
  - Exclude<T, K>：這個內建工具類型會從 T 中排除當前的 K。例如，如果 T 是 'A' | 'B' | 'C'，且當前 K 是 'A'，那麼 Exclude<T, K> 將返回 'B' | 'C'。
  - Permutation<Exclude<T, K>>：對剩餘的元素進行遞迴排列。這樣，對於每一個選取的 K，我們都會生成剩下元素的所有排列。
  - ...：展開運算符，將遞迴返回的結果展開並添加到當前 K 前面，形成一個新的元組。
兌現無法到達的類型 (Fallback Case)
: never:
這是條件型別的回退情況，當上述條件不滿足時返回 never。在這個上下文中，這行代碼不會被執行，因為前面的條件已經涵蓋了所有可能的情況。
為什麼要這樣寫？: 這一行的存在是為了確保類型系統的一致性，並在未滿足條件時給出明確的錯誤。

額外補充：

關於分配條件類型 (Distributive Conditional Types)

首先 What is “distributive” ? :

*An operation that produces the same result when applied to an entire expression as when applied individually to each part and then combining the results.

(such as multiplication in a(b + c) = ab + ac)

When conditional types act on a generic type, they become distributive when given a union type. For example, take the following:
```
type ToArray<Type> = Type extends any ? Type[] : never;
```
If we plug a union type into ToArray, then the conditional type will be applied to each member of that union.
```
type ToArray<Type> = Type extends any ? Type[] : never;

type StrArrOrNumArr = ToArray<string | number>;
           //^? type StrArrOrNumArr = string[] | number[]
```
What happens here is that ToArray distributes on:
```
string | number;
```
and maps over each member type of the union, to what is effectively:
```
ToArray<string> | ToArray<number>;
```
which leaves us with:
```
string[] | number[];
```
Typically, distributivity is the desired behavior. To avoid that behavior, you can surround each side of the extends keyword with square brackets.
```
type ToArrayNonDist<Type> = [Type] extends [any] ? Type[] : never;

// 'ArrOfStrOrNum' is no longer a union.
type ArrOfStrOrNum = ToArrayNonDist<string | number>;
         //^? type ArrOfStrOrNum = (string | number)[]
```