我們如何在不產生所有前面的排列的情況下直接找到集合的第 N 個排列？

直接取得第n 個排列

任務是找到一組元素的第n 個排列，而無需明確計算所有元素之前的排列。這可以使用稱為因子演算法的巧妙演算法來實現。

因子演算法利用排列索引的階乘分解。透過對階乘數重複進行歐幾裡得除法，我們得到一組代表排列的商。

演算法的工作原理如下：

1. 階乘分解：將排列索引n 除以(n-1)!、(n-2)! 的階乘，依此類推在。商儲存在數組中。
2. 排列表示： 每個商表示從剩餘元素中選擇的元素的索引。
3. 調整： 由於商不考慮前面的值，因此需要調整它們以反映正確的排列。將每個商增加小於或等於它的前面商的數量。

例如，讓我們找出 {'A', 'B', 'C'} 的第三個排列。

• n = 3
• 商：[1, 0, 0]
• 調整後的商數：[1, 0, 1]

調整後的商數：[1, 0, 1]

排列因此為'B', 'A', 'C'，這確實是的第三個排列給定的集合。

提供的 C 程式碼實作了因子演算法，示範如何取得直接進行第 n 次排列，無需計算先前的排列。

以上是我們如何在不產生所有前面的排列的情況下直接找到集合的第 N 個排列？的詳細內容。更多資訊請關注PHP中文網其他相關文章！