辨識n 次排列的高效演算法
給定一個表示排列的元素數組，本題探討了一種演算法的可能性有效計算第 n個排列，無需計算所有前面的排列
因式排列分解
此解決方案利用了因式分解的概念。透過執行階乘的連續除法，它將排列索引分解為商數序列。此序列表示所需的排列。
調整商
但是，初始商忽略先前值的影響。因此，調整步驟是必要的。對於每個商，它都會透過較小或等於前面商的計數來增加值。
實現
提供了算法的C 實現下面：
void ithPermutation(const int n, int i) {
int *fact = new int[n], *perm = new int[n];
// Compute factorials
fact[0] = 1;
for (int k = 1; k < n; k++)
fact[k] = fact[k - 1] * k;
// Compute factorial code
for (int k = 0; k < n; k++) {
perm[k] = i / fact[n - 1 - k];
i %= fact[n - 1 - k];
}
// Adjust values for permutation
for (int k = n - 1; k > 0; k--)
for (int j = k - 1; j >= 0; j--)
if (perm[j] <= perm[k])
perm[k]++;
// Print permutation
for (int k = 0; k < n; k++)
cout << perm[k] << " ";
cout << "\n";
delete[] fact;
delete[] perm;
}示例
例如，ithPermutation(10, 3628799)傳回十個元素的最後一個排列：
9 8 7 6 5 4 3 2 1 0
以上是我們如何有效地找到集合的第n個排列？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
