生成集合的排列（最有效）

Question

我想生成一个集合（集合）的所有排列，如下所示：Collection: 1, 2, 3Permutations: {1, 2, 3}              {1, 3, 2}              {2, 1, 3}              {2, 3, 1}              {3, 1, 2}              {3, 2, 1}一般而言，这不是“如何”的问题，而是关于如何最有效的问题。此外，我不想生成所有排列并返回它们，但一次只生成一个排列，并且只在必要时继续（很像迭代器 - 我也尝试过，但结果却少了有效）。我已经测试了很多算法和方法，并提出了这个代码，这是我尝试过的最有效的代码：public static bool NextPermutation<T>(T[] elements) where T : IComparable<T>{    // More efficient to have a variable instead of accessing a property    var count = elements.Length;    // Indicates whether this is the last lexicographic permutation    var done = true;    // Go through the array from last to first    for (var i = count - 1; i > 0; i--)    {        var curr = elements[i];        // Check if the current element is less than the one before it        if (curr.CompareTo(elements[i - 1]) < 0)        {            continue;        }        // An element bigger than the one before it has been found,        // so this isn't the last lexicographic permutation.        done = false;        // Save the previous (bigger) element in a variable for more efficiency.        var prev = elements[i - 1];            {                curr = tmp;                currIndex = j;            }        }}它的用法是发送一个元素数组，然后返回一个布尔值，指示这是否是最后一个词典排列，以及将数组改为下一个排列。用法示例：var arr = new[] {1, 2, 3};PrintArray(arr);while (!NextPermutation(arr)){    PrintArray(arr);}问题是我对代码的速度感到不满意。迭代大小为11的数组的所有排列大约需要4秒。虽然它可以被认为是令人印象深刻的，因为一组11号的可能排列量11!接近4000万。逻辑上，对于大小为12的数组，它将花费大约12倍的时间，因为12!是11! * 12，并且对于大小为13的数组，它将花费大约13倍于12大小的时间，依此类推。所以你可以很容易地理解如何使用12或更大的数组，它需要很长时间才能完成所有排列。而且我有一种强烈的预感，我可以以某种方式减少那么多的时间（没有切换到C＃以外的语言 - 因为编译器优化确实非常好地优化，我怀疑我可以在Assembly中手动优化）。有没有人知道以其他方式更快地完成这项工作？您是否知道如何使当前算法更快？请注意，我不想使用外部库或服务来实现这一点 - 我希望拥有代码本身，并希望它尽可能高效。

Answer 1

这可能就是你要找的东西。

    private static bool NextPermutation(int[] numList)

    {

        /*

         Knuths

         1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.

         2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.

         3. Swap a[j] with a[l].

         4. Reverse the sequence from a[j + 1] up to and including the final element a[n].

         */

        var largestIndex = -1;

        for (var i = numList.Length - 2; i >= 0; i--)

        {

            if (numList[i] < numList[i + 1]) {

                largestIndex = i;

                break;

            }

        }

        if (largestIndex < 0) return false;

        var largestIndex2 = -1;

        for (var i = numList.Length - 1 ; i >= 0; i--) {

            if (numList[largestIndex] < numList[i]) {

                largestIndex2 = i;

                break;

            }

        }

        var tmp = numList[largestIndex];

        numList[largestIndex] = numList[largestIndex2];

        numList[largestIndex2] = tmp;

        for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--) {

            tmp = numList[i];

            numList[i] = numList[j];

            numList[j] = tmp;

        }

        return true;

    }