c# - 生成集合的排列(最有效)

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];

        // Have a variable to hold the index of the element to swap
        // with the previous element (the to-swap element would be
        // the smallest element that comes after the previous element
        // and is bigger than the previous element), initializing it
        // as the current index of the current item (curr).
        var currIndex = i;

        // Go through the array from the element after the current one to last
        for (var j = i + 1; j < count; j++)
        {
            // Save into variable for more efficiency
            var tmp = elements[j];

            // Check if tmp suits the "next swap" conditions:
            // Smallest, but bigger than the "prev" element
            if (tmp.CompareTo(curr) < 0 && tmp.CompareTo(prev) > 0)
            {
                curr = tmp;
                currIndex = j;
            }
        }

        // Swap the "prev" with the new "curr" (the swap-with element)
        elements[currIndex] = prev;
        elements[i - 1] = curr;

        // Reverse the order of the tail, in order to reset it's lexicographic order
        for (var j = count - 1; j > i; j--, i++)
        {
            var tmp = elements[j];
            elements[j] = elements[i];
            elements[i] = tmp;
        }

        // Break since we have got the next permutation
        // The reason to have all the logic inside the loop is
        // to prevent the need of an extra variable indicating "i" when
        // the next needed swap is found (moving "i" outside the loop is a
        // bad practice, and isn't very readable, so I preferred not doing
        // that as well).
        break;
    }

    // Return whether this has been the last lexicographic permutation.
    return done;
}

它的用法是发送一个元素数组，并返回一个 bool 值，指示这是否是最后一个字典顺序排列，以及将数组更改为下一个排列。

使用示例:

var arr = new[] {1, 2, 3};

PrintArray(arr);

while (!NextPermutation(arr))
{
    PrintArray(arr);
}

问题是我对代码的速度不满意。

迭代大小为 11 的数组的所有排列大约需要 4 秒。虽然它可以被认为是令人印象深刻的，因为一组大小为 11 的可能排列的数量是 11!，这将近 4000 万。

从逻辑上讲，对于大小为 12 的数组，它将花费大约 12 倍的时间，因为 12! 是 11! * 12，对于大小为 13 的数组，它所花费的时间是大小为 12 所花费时间的大约 13 倍，依此类推。

因此您可以很容易地理解对于大小为 12 或更大的数组，完成所有排列确实需要很长时间。

而且我有一种强烈的预感，我可以以某种方式大大缩短时间(无需切换到 C# 以外的语言 - 因为编译器优化确实可以很好地优化，我怀疑我是否可以手动优化，组装)。

有没有人知道任何其他方法可以更快地完成这项工作？您对如何使当前算法更快有任何想法吗？

请注意，我不想为此使用外部库或服务 - 我想要代码本身，我希望它尽可能高效。

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;
    }