首页 >后端开发 >php教程 >我们如何有效地找到集合的第n个排列?

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

Linda Hamilton
Linda Hamilton原创
2024-12-07 06:46:16366浏览

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

9 8 7 6 5 4 3 2 1 0

以上是我们如何有效地找到集合的第n个排列?的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn