我們如何有效地找到集合的第n個排列？

辨識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中文網其他相關文章！