一、排列 (Permutation)
（一）概念
 |
| 1234的排列示意圖，共有4!種 |
上圖為1234的排列示意圖，共有4!種可能，4x3x2x1=24，這裡swap()內的參數是指index：
- 第1層有4種可能，分別為swap(1, 1)、swap(1, 2)、swap(1, 3)、swap(1, 4)
- 第2層有3種可能，分別為swap(2, 2)、swap(2, 3)、swap(2, 4)
- 第3層有2種可能，分別為swap(3, 3)、swap(3, 4)
- 第4層有1種可能，分別為swap(4, 4)
從以上swap()的情況是有規律性的，在第i層中：
- 會swap (n-i+1)次，即i和i, i+1, i+2, ...n swap
- swap的範圍為i (head) ~ n (tail)
（二）實作
 |
| 排列 程式碼 |
因此可以使用遞迴和迴圈去排有系統的排列去所有可能，在C++ <algorithm>中，有std::next_permutation(BidirectionalIterator first, BidirectionalIterator last)可以去排列出所有可能，必要的參數為容器範圍和容器本身，因為iterator本身指向容器，故只需頭、尾即滿足必要的資訊。
二、第k個排列
（一）實作
 |
| 第k個排列 程式碼 |
如果我們要在n長度的排列中，找到第k個排列，該如何快速地得到？用列舉法是一個可行的方法，但不是個聰明的方式。如果n = 4，會有24種排法，每一種排法都是獨特的。如果要找n = 4、k = 2的排列則為1243。
可以發現1243只有swap(3, 4)，可以發現一開始的swap都是從後面開始，慢慢會往前面字元swap，且會越來越頻繁和複雜。所以在第2排列中，第1, 2字元都是沒被動過的，而第3, 4字元有被swap。
所以在第1+1排列中，會動到第3字元；那要多久的時間才會動到第2字元呢？第2+1排列；那第1字元呢？第6+1排列；等等1, 2, 6是什麼神秘數列？答案是階乘 (factorial)。所以一開始我們會先算出(n-1)!，然後依序(n-2)!, (n-3)!, ....
接下來會用k/fact，去預估第i字元有沒有被動過，如果沒有被動過會得到0，如果有被動過就為非0，接下來去更新我們數字列、階乘、k值。
三、相關文章
請詳見LeetCode相關文章
留言
張貼留言