我们如何有效地找到集合的第n个排列？-php教程-PHP中文网

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

Linda Hamilton

发布： 2024-12-07 06:46:16

原创

344 人浏览过

How Can We Efficiently Find the n-th Permutation of a Set?

识别 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) 返回十个元素的最后一个排列：