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

Question

我想生成一个集合（集合）的所有排列，如下所示：

Collection: 1, 2, 3

Permutations: {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

这可能就是你要找的东西。&nbsp; &nbsp; private static bool NextPermutation(int[] numList)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; /*&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Knuths&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;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.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;3. Swap a[j] with a[l].&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;4. Reverse the sequence from a[j + 1] up to and including the final element a[n].&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; &nbsp; &nbsp; var largestIndex = -1;&nbsp; &nbsp; &nbsp; &nbsp; for (var i = numList.Length - 2; i >= 0; i--)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (numList[i] < numList[i + 1]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; largestIndex = i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if (largestIndex < 0) return false;&nbsp; &nbsp; &nbsp; &nbsp; var largestIndex2 = -1;&nbsp; &nbsp; &nbsp; &nbsp; for (var i = numList.Length - 1 ; i >= 0; i--) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (numList[largestIndex] < numList[i]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; largestIndex2 = i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; var tmp = numList[largestIndex];&nbsp; &nbsp; &nbsp; &nbsp; numList[largestIndex] = numList[largestIndex2];&nbsp; &nbsp; &nbsp; &nbsp; numList[largestIndex2] = tmp;&nbsp; &nbsp; &nbsp; &nbsp; for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tmp = numList[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; numList[i] = numList[j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; numList[j] = tmp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; }