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

Generating permutations of a set (most efficiently)

提问by SimpleVar

I would like to generate all permutations of a set (a collection), like so:

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

Collection: 1, 2, 3
Permutations: {1, 2, 3}
              {1, 3, 2}
              {2, 1, 3}
              {2, 3, 1}
              {3, 1, 2}
              {3, 2, 1}

This isn't a question of "how", in general, but more about how most efficiently. Also, I wouldn't want to generate ALL permutations and return them, but only generating a single permutation, at a time, and continuing only if necessary (much like Iterators - which I've tried as well, but turned out to be less efficient).

一般来说，这不是“如何”的问题，而是更多关于如何最有效的问题。另外，我不想生成所有排列并返回它们，而是一次只生成一个排列，并且仅在必要时才继续（很像迭代器 - 我也尝试过，但结果证明更少高效的）。

I've tested many algorithms and approaches and came up with this code, which is most efficient of those I tried:

我测试了许多算法和方法，并提出了以下代码，这是我尝试过的最有效的代码：

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

It's usage would be sending an array of elements, and getting back a boolean indicating whether this was the last lexicographical permutation or not, as well as having the array altered to the next permutation.

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

Usage example:

用法示例：

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

PrintArray(arr);

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

The thing is that I'm not happy with the speed of the code.

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

Iterating over all permutations of an array of size 11 takes about 4 seconds. Although it could be considered impressive, since the amount of possible permutations of a set of size 11 is 11!which is nearly 40 million.

迭代大小为 11 的数组的所有排列大约需要 4 秒。尽管这可能令人印象深刻，因为一组大小为 11 的可能排列的数量11!接近 4000 万。

Logically, with an array of size 12 it will take about 12 times more time, since 12!is 11! * 12, and with an array of size 13 it will take about 13 times more time than the time it took with size 12, and so on.

从逻辑上讲，使用大小为 12 的数组将花费大约 12 倍的时间，因为12!is 11! * 12，使用大小为 13 的数组将花费大约为大小为 12 的时间的 13 倍，依此类推。

So you can easily understand how with an array of size 12 and more, it really takes a very long time to go through all permutations.

因此，您可以轻松理解如何使用大小为 12 或更大的数组，完成所有排列确实需要很长时间。

And I have a strong hunch that I can somehow cut that time by a lot (without switching to a language other than C# - because compiler optimization really does optimize pretty nicely, and I doubt I could optimize as good, manually, in Assembly).

而且我有一种强烈的预感，我可以以某种方式将这段时间缩短很多（无需切换到 C# 以外的语言 - 因为编译器优化确实优化得非常好，我怀疑我是否可以在汇编中手动优化得一样好）。

Does anyone know any other way to get that done faster? Do you have any idea as to how to make the current algorithm faster?

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

Note that I don't want to use an external library or service in order to do that - I want to have the code itself and I want it to be as efficient as humanly possible.

请注意，我不想使用外部库或服务来做到这一点 - 我想要代码本身，并且我希望它尽可能高效。

采纳答案by Eric Ouellet

Update 2018-05-28:

• A new multithreaded version (lot faster) is available below as another answer.
• Also an article about permutation: Permutations: Fast implementations and a new indexing algorithm allowing multithreading

2018-05-28 更新：

• 下面提供了一个新的多线程版本（速度更快）作为另一个答案。
• 还有一篇关于排列的文章：排列：快速实现和允许多线程的新索引算法

A little bit too late...

有点晚了...

According to recent tests (updated 2018-05-22)

根据最近的测试（2018-05-22更新）

• Fastest is mine BUT not in lexicographic order
• For fastest lexicographic order, Sani Singh Huttunen solution seems to be the way to go.

• 最快的是我的，但不是按字典顺序排列的
• 对于最快的字典顺序，Sani Singh Huttunen 解决方案似乎是要走的路。

Performance test results for 10 items (10!) in release on my machine (millisecs):

在我的机器上发布的 10 个项目（10！）的性能测试结果（毫秒）：

• Ouellet : 29
• SimpleVar: 95
• Erez Robinson : 156
• Sani Singh Huttunen : 37
• Pengyang : 45047

• 欧莱特 : 29
• 简单变量：95
• 埃雷兹罗宾逊：156
• 萨尼·辛格·胡图宁：37
• 彭阳：45047

Performance test results for 13 items (13!) in release on my machine (seconds):

在我的机器上发布的 13 个项目（13 个！）的性能测试结果（秒）：

• Ouellet : 48.437
• SimpleVar: 159.869
• Erez Robinson : 327.781
• Sani Singh Huttunen : 64.839

• 欧莱特 : 48.437
• 简单变量：159.869
• 埃雷兹罗宾逊：327.781
• Sani Singh Huttunen : 64.839

---

---

Advantages of my solution:

我的解决方案的优点：

• Heap's algorithm (Single swap per permutation)
• No multiplication (like some implementations seen on the web)
• Inlined swap
• Generic
• No unsafe code
• In place (very low memory usage)
• No modulo (only first bit compare)

• 堆算法（每排列单交换）
• 没有乘法（就像在网络上看到的一些实现）
• 内联交换
• 通用的
• 没有不安全的代码
• 就地（非常低的内存使用量）
• 无模（仅第一位比较）

My implementation of Heap's algorithm:

我对堆算法的实现：

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;

namespace WpfPermutations
{
    /// <summary>
    /// EO: 2016-04-14
    /// Generator of all permutations of an array of anything.
    /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
    /// </summary>
    public static class Permutations
    {
        /// <summary>
        /// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
        /// </summary>
        /// <param name="items">Items to permute in each possible ways</param>
        /// <param name="funcExecuteAndTellIfShouldStop"></param>
        /// <returns>Return true if cancelled</returns> 
        public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
        {
            int countOfItem = items.Length;

            if (countOfItem <= 1)
            {
                return funcExecuteAndTellIfShouldStop(items);
            }

            var indexes = new int[countOfItem];
            for (int i = 0; i < countOfItem; i++)
            {
                indexes[i] = 0;
            }

            if (funcExecuteAndTellIfShouldStop(items))
            {
                return true;
            }

            for (int i = 1; i < countOfItem;)
            {
                if (indexes[i] < i)
                { // On the web there is an implementation with a multiplication which should be less efficient.
                    if ((i & 1) == 1) // if (i % 2 == 1)  ... more efficient ??? At least the same.
                    {
                        Swap(ref items[i], ref items[indexes[i]]);
                    }
                    else
                    {
                        Swap(ref items[i], ref items[0]);
                    }

                    if (funcExecuteAndTellIfShouldStop(items))
                    {
                        return true;
                    }

                    indexes[i]++;
                    i = 1;
                }
                else
                {
                    indexes[i++] = 0;
                }
            }

            return false;
        }

        /// <summary>
        /// This function is to show a linq way but is far less efficient
        /// From: StackOverflow user: Pengyang : http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        /// <param name="length"></param>
        /// <returns></returns>
        static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
        {
            if (length == 1) return list.Select(t => new T[] { t });

            return GetPermutations(list, length - 1)
                .SelectMany(t => list.Where(e => !t.Contains(e)),
                    (t1, t2) => t1.Concat(new T[] { t2 }));
        }

        /// <summary>
        /// Swap 2 elements of same type
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="a"></param>
        /// <param name="b"></param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void Swap<T>(ref T a, ref T b)
        {
            T temp = a;
            a = b;
            b = temp;
        }

        /// <summary>
        /// Func to show how to call. It does a little test for an array of 4 items.
        /// </summary>
        public static void Test()
        {
            ForAllPermutation("123".ToCharArray(), (vals) =>
            {
                Console.WriteLine(String.Join("", vals));
                return false;
            });

            int[] values = new int[] { 0, 1, 2, 4 };

            Console.WriteLine("Ouellet heap's algorithm implementation");
            ForAllPermutation(values, (vals) =>
            {
                Console.WriteLine(String.Join("", vals));
                return false;
            });

            Console.WriteLine("Linq algorithm");
            foreach (var v in GetPermutations(values, values.Length))
            {
                Console.WriteLine(String.Join("", v));
            }

            // Performance Heap's against Linq version : huge differences
            int count = 0;

            values = new int[10];
            for (int n = 0; n < values.Length; n++)
            {
                values[n] = n;
            }

            Stopwatch stopWatch = new Stopwatch();

            ForAllPermutation(values, (vals) =>
            {
                foreach (var v in vals)
                {
                    count++;
                }
                return false;
            });

            stopWatch.Stop();
            Console.WriteLine($"Ouellet heap's algorithm implementation {count} items in {stopWatch.ElapsedMilliseconds} millisecs");

            count = 0;
            stopWatch.Reset();
            stopWatch.Start();

            foreach (var vals in GetPermutations(values, values.Length))
            {
                foreach (var v in vals)
                {
                    count++;
                }
            }

            stopWatch.Stop();
            Console.WriteLine($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
        }
    }
}

An this is my test code:

这是我的测试代码：

Task.Run(() =>
            {

                int[] values = new int[12];
                for (int n = 0; n < values.Length; n++)
                {
                    values[n] = n;
                }

                // Eric Ouellet Algorithm
                int count = 0;
                var stopwatch = new Stopwatch();
                stopwatch.Reset();
                stopwatch.Start();
                Permutations.ForAllPermutation(values, (vals) =>
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                    return false;
                });
                stopwatch.Stop();
                Console.WriteLine($"This {count} items in {stopwatch.ElapsedMilliseconds} millisecs");

                // Simple Plan Algorithm
                count = 0;
                stopwatch.Reset();
                stopwatch.Start();
                PermutationsSimpleVar permutations2 = new PermutationsSimpleVar();
                permutations2.Permutate(1, values.Length, (int[] vals) =>
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                });
                stopwatch.Stop();
                Console.WriteLine($"Simple Plan {count} items in {stopwatch.ElapsedMilliseconds} millisecs");

                // ErezRobinson Algorithm
                count = 0;
                stopwatch.Reset();
                stopwatch.Start();
                foreach(var vals in PermutationsErezRobinson.QuickPerm(values))
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                };
                stopwatch.Stop();
                Console.WriteLine($"Erez Robinson {count} items in {stopwatch.ElapsedMilliseconds} millisecs");
            });

Usage examples:

用法示例：

ForAllPermutation("123".ToCharArray(), (vals) =>
    {
        Console.WriteLine(String.Join("", vals));
        return false;
    });

int[] values = new int[] { 0, 1, 2, 4 };
ForAllPermutation(values, (vals) =>
        {
            Console.WriteLine(String.Join("", vals));
            return false;
        });

回答by Sani Singh Huttunen

This might be what you're looking for.

这可能就是你要找的。

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

回答by Erez Robinson

The fastest permutation algorithm that i know of is the QuickPerm algorithm.
Here is the implementation, it uses yield return so you can iterate one at a time like required.

我所知道的最快的置换算法是 QuickPerm 算法。
这是实现，它使用收益回报，因此您可以根据需要一次迭代一个。

Code:

代码：

public static IEnumerable<IEnumerable<T>> QuickPerm<T>(this IEnumerable<T> set)
    {
        int N = set.Count();
        int[] a = new int[N];
        int[] p = new int[N];

        var yieldRet = new T[N];

        List<T> list = new List<T>(set);

        int i, j, tmp; // Upper Index i; Lower Index j

        for (i = 0; i < N; i++)
        {
            // initialize arrays; a[N] can be any type
            a[i] = i + 1; // a[i] value is not revealed and can be arbitrary
            p[i] = 0; // p[i] == i controls iteration and index boundaries for i
        }
        yield return list;
        //display(a, 0, 0);   // remove comment to display array a[]
        i = 1; // setup first swap points to be 1 and 0 respectively (i & j)
        while (i < N)
        {
            if (p[i] < i)
            {
                j = i%2*p[i]; // IF i is odd then j = p[i] otherwise j = 0
                tmp = a[j]; // swap(a[j], a[i])
                a[j] = a[i];
                a[i] = tmp;

                //MAIN!

                for (int x = 0; x < N; x++)
                {
                    yieldRet[x] = list[a[x]-1];
                }
                yield return yieldRet;
                //display(a, j, i); // remove comment to display target array a[]

                // MAIN!

                p[i]++; // increase index "weight" for i by one
                i = 1; // reset index i to 1 (assumed)
            }
            else
            {
                // otherwise p[i] == i
                p[i] = 0; // reset p[i] to zero
                i++; // set new index value for i (increase by one)
            } // if (p[i] < i)
        } // while(i < N)
    }

回答by Colonel Panic

There's an accessible introduction to the algorithms and survey of implementations in Steven Skiena's Algorithm Design Manual(chapter 14.4 in the second edition)

Steven Skiena 的算法设计手册（第二版中的第 14.4 章）中提供了对算法和实现调查的可访问介绍

Skiena references D. Knuth. The Art of Computer Programming, Volume 4 Fascicle 2: Generating All Tuples and Permutations. Addison Wesley, 2005.

Skiena 引用了 D. Knuth。计算机编程艺术，第 4 卷分册 2：生成所有元组和排列。艾迪生·韦斯利，2005 年。

回答by btilly

I would be surprised if there are really order of magnitude improvements to be found. If there are, then C# needs fundamental improvement. Furthermore doing anything interesting with your permutation will generally take more work than generating it. So the cost of generating is going to be insignificant in the overall scheme of things.

如果真的能找到数量级的改进，我会感到惊讶。如果有，那么 C# 需要根本的改进。此外，用你的排列做任何有趣的事情通常比生成它需要更多的工作。因此，在整体方案中，发电成本将是微不足道的。

That said, I would suggest trying the following things. You have already tried iterators. But have you tried having a function that takes a closure as input, then then calls that closure for each permutation found? Depending on internal mechanics of C#, this may be faster.

也就是说，我建议尝试以下事情。您已经尝试过迭代器。但是您是否尝试过使用一个函数将闭包作为输入，然后为找到的每个排列调用该闭包？根据 C# 的内部机制，这可能会更快。

Similarly, have you tried having a function that returns a closure that will iterate over a specific permutation?

同样，您是否尝试过有一个函数返回一个将迭代特定排列的闭包？

With either approach, there are a number of micro-optimizations you can experiment with. For instance you can sort your input array, and after that you always know what order it is in. For example you can have an array of bools indicating whether that element is less than the next one, and rather than do comparisons, you can just look at that array.

无论采用哪种方法，您都可以尝试多种微优化。例如，您可以对输入数组进行排序，之后您始终知道它的顺序。例如，您可以拥有一个布尔数组，指示该元素是否小于下一个元素，而不是进行比较，您可以看看那个数组。

回答by Mike Dunlavey

Well, if you can handle it in C and then translate to your language of choice, you can't really go much faster than this, because the time will be dominated by print:

好吧，如果你能用 C 处理它然后翻译成你选择的语言，你真的不能比这快得多，因为时间将被print：

void perm(char* s, int n, int i){
  if (i >= n-1) print(s);
  else {
    perm(s, n, i+1);
    for (int j = i+1; j<n; j++){
      swap(s[i], s[j]);
      perm(s, n, i+1);
      swap(s[i], s[j]);
    }
  }
}

perm("ABC", 3, 0);

回答by Sam

Here is a generic permutation finder that will iterate through every permutation of a collection and call an evalution function. If the evalution function returns true (it found the answer it was looking for), the permutation finder stops processing.

这是一个通用的排列查找器，它将遍历集合的每个排列并调用评估函数。如果评估函数返回 true（它找到了它正在寻找的答案），置换查找器将停止处理。

public class PermutationFinder<T>
{
    private T[] items;
    private Predicate<T[]> SuccessFunc;
    private bool success = false;
    private int itemsCount;

    public void Evaluate(T[] items, Predicate<T[]> SuccessFunc)
    {
        this.items = items;
        this.SuccessFunc = SuccessFunc;
        this.itemsCount = items.Count();

        Recurse(0);
    }

    private void Recurse(int index)
    {
        T tmp;

        if (index == itemsCount)
            success = SuccessFunc(items);
        else
        {
            for (int i = index; i < itemsCount; i++)
            {
                tmp = items[index];
                items[index] = items[i];
                items[i] = tmp;

                Recurse(index + 1);

                if (success)
                    break;

                tmp = items[index];
                items[index] = items[i];
                items[i] = tmp;
            }
        }
    }
}

Here is a simple implementation:

这是一个简单的实现：

class Program
{
    static void Main(string[] args)
    {
        new Program().Start();
    }

    void Start()
    {
        string[] items = new string[5];
        items[0] = "A";
        items[1] = "B";
        items[2] = "C";
        items[3] = "D";
        items[4] = "E";
        new PermutationFinder<string>().Evaluate(items, Evaluate);
        Console.ReadLine();
    }

    public bool Evaluate(string[] items)
    {
        Console.WriteLine(string.Format("{0},{1},{2},{3},{4}", items[0], items[1], items[2], items[3], items[4]));
        bool someCondition = false;

        if (someCondition)
            return true;  // Tell the permutation finder to stop.

        return false;
    }
}

回答by SimpleVar

Here is the fastest implementation I ended up with:

这是我最终得到的最快的实现：

public class Permutations
{
    private readonly Mutex _mutex = new Mutex();

    private Action<int[]> _action;
    private Action<IntPtr> _actionUnsafe;
    private unsafe int* _arr;
    private IntPtr _arrIntPtr;
    private unsafe int* _last;
    private unsafe int* _lastPrev;
    private unsafe int* _lastPrevPrev;

    public int Size { get; private set; }

    public bool IsRunning()
    {
        return this._mutex.SafeWaitHandle.IsClosed;
    }

    public bool Permutate(int start, int count, Action<int[]> action, bool async = false)
    {
        return this.Permutate(start, count, action, null, async);
    }

    public bool Permutate(int start, int count, Action<IntPtr> actionUnsafe, bool async = false)
    {
        return this.Permutate(start, count, null, actionUnsafe, async);
    }

    private unsafe bool Permutate(int start, int count, Action<int[]> action, Action<IntPtr> actionUnsafe, bool async = false)
    {
        if (!this._mutex.WaitOne(0))
        {
            return false;
        }

        var x = (Action)(() =>
                             {
                                 this._actionUnsafe = actionUnsafe;
                                 this._action = action;

                                 this.Size = count;

                                 this._arr = (int*)Marshal.AllocHGlobal(count * sizeof(int));
                                 this._arrIntPtr = new IntPtr(this._arr);

                                 for (var i = 0; i < count - 3; i++)
                                 {
                                     this._arr[i] = start + i;
                                 }

                                 this._last = this._arr + count - 1;
                                 this._lastPrev = this._last - 1;
                                 this._lastPrevPrev = this._lastPrev - 1;

                                 *this._last = count - 1;
                                 *this._lastPrev = count - 2;
                                 *this._lastPrevPrev = count - 3;

                                 this.Permutate(count, this._arr);
                             });

        if (!async)
        {
            x();
        }
        else
        {
            new Thread(() => x()).Start();
        }

        return true;
    }

    private unsafe void Permutate(int size, int* start)
    {
        if (size == 3)
        {
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();
            Swap(this._last, this._lastPrevPrev);
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();
            Swap(this._last, this._lastPrevPrev);
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();

            return;
        }

        var sizeDec = size - 1;
        var startNext = start + 1;
        var usedStarters = 0;

        for (var i = 0; i < sizeDec; i++)
        {
            this.Permutate(sizeDec, startNext);

            usedStarters |= 1 << *start;

            for (var j = startNext; j <= this._last; j++)
            {
                var mask = 1 << *j;

                if ((usedStarters & mask) != mask)
                {
                    Swap(start, j);
                    break;
                }
            }
        }

        this.Permutate(sizeDec, startNext);

        if (size == this.Size)
        {
            this._mutex.ReleaseMutex();
        }
    }

    private unsafe void DoAction()
    {
        if (this._action == null)
        {
            if (this._actionUnsafe != null)
            {
                this._actionUnsafe(this._arrIntPtr);
            }

            return;
        }

        var result = new int[this.Size];

        fixed (int* pt = result)
        {
            var limit = pt + this.Size;
            var resultPtr = pt;
            var arrayPtr = this._arr;

            while (resultPtr < limit)
            {
                *resultPtr = *arrayPtr;
                resultPtr++;
                arrayPtr++;
            }
        }

        this._action(result);
    }

    private static unsafe void Swap(int* a, int* b)
    {
        var tmp = *a;
        *a = *b;
        *b = tmp;
    }
}

Usage and testing performance:

使用及测试性能：

var perms = new Permutations();

var sw1 = Stopwatch.StartNew();

perms.Permutate(0,
                11,
                (Action<int[]>)null); // Comment this line and...
                //PrintArr); // Uncomment this line, to print permutations

sw1.Stop();
Console.WriteLine(sw1.Elapsed);

Printing method:

印刷方式：

private static void PrintArr(int[] arr)
{
    Console.WriteLine(string.Join(",", arr));
}

Going deeper:

更深入：

I did not even think about this for a very long time, so I can only explain my code so much, but here's the general idea:

很长一段时间我什至没有想到这个，所以我只能解释我的代码，但总体思路如下：

1. Permutations aren't lexicographic - this allows me to practically perform less operations between permutations.
2. The implementation is recursive, and when the "view" size is 3, it skips the complex logic and just performs 6 swaps to get the 6 permutations (or sub-permutations, if you will).
3. Because the permutations aren't in a lexicographic order, how can I decide which element to bring to the start of the current "view" (sub permutation)? I keep record of elements that were already used as "starters" in the current sub-permutation recursive call and simply search linearly for one that wasn't used in the tail of my array.
4. The implementation is for integers only, so to permute over a generic collection of elements you simply use the Permutations class to permute indices instead of your actual collection.
5. The Mutex is there just to ensure things don't get screwed when the execution is asynchronous (notice that you can pass an UnsafeAction parameter that will in turn get a pointer to the permuted array. You must not change the order of elements in that array (pointer)! If you want to, you should copy the array to a tmp array or just use the safe action parameter which takes care of that for you - the passed array is already a copy).

1. 排列不是按字典顺序排列的 - 这使我实际上可以在排列之间执行较少的操作。
2. 实现是递归的，当“视图”大小为 3 时，它跳过复杂的逻辑，只执行 6 次交换以获得 6 个排列（或子排列，如果你愿意的话）。
3. 因为排列不是按字典顺序排列的，我如何决定将哪个元素带到当前“视图”（子排列）的开头？我记录了在当前子排列递归调用中已经被用作“启动器”的元素，并简单地线性搜索我的数组尾部未使用的元素。
4. 该实现仅适用于整数，因此要置换通用元素集合，您只需使用 Permutations 类置换索引而不是您的实际集合。
5. Mutex 只是为了确保在异步执行时不会搞砸事情（请注意，您可以传递一个 UnsafeAction 参数，该参数将依次获得指向置换数组的指针。您不得更改该数组中元素的顺序（指针）！如果你愿意，你应该将数组复制到一个 tmp 数组，或者只使用为你处理这个问题的安全操作参数 - 传递的数组已经是一个副本）。

Note:

笔记：

I have no idea how good this implementation really is - I haven't touched it in so long. Test and compare to other implementations on your own, and let me know if you have any feedback!

我不知道这个实现到底有多好 - 我已经很久没有接触过它了。自己测试并与其他实现进行比较，如果您有任何反馈，请告诉我！

Enjoy.

享受。

回答by Antoine Comeau

I created an algorithm slightly faster than Knuth's one:

我创建了一个比 Knuth 的算法略快的算法：

11 elements:

mine: 0.39 seconds

Knuth's: 0.624 seconds

13 elements:

mine: 56.615 seconds

Knuth's: 98.681 seconds

11个要素：

我的：0.39 秒

克努斯：0.624 秒

13个要素：

我的：56.615 秒

克努斯：98.681 秒

Here's my code in Java:

这是我的 Java 代码：

public static void main(String[] args)
{
    int n=11;
    int a,b,c,i,tmp;
    int end=(int)Math.floor(n/2);
    int[][] pos = new int[end+1][2];
    int[] perm = new int[n];

    for(i=0;i<n;i++) perm[i]=i;

    while(true)
    {
        //this is where you can use the permutations (perm)
        i=0;
        c=n;

        while(pos[i][1]==c-2 && pos[i][0]==c-1)
        {
            pos[i][0]=0;
            pos[i][1]=0;
            i++;
            c-=2;
        }

        if(i==end) System.exit(0);

        a=(pos[i][0]+1)%c+i;
        b=pos[i][0]+i;

        tmp=perm[b];
        perm[b]=perm[a];
        perm[a]=tmp;

        if(pos[i][0]==c-1)
        {
            pos[i][0]=0;
            pos[i][1]++;
        }
        else
        {
            pos[i][0]++;
        }
    }
}

The problem is my algorithm only works for odd numbers of elements. I wrote this code quickly so I'm pretty sure there's a better way to implement my idea to get better performance, but I don't really have the time to work on it right now to optimize it and solve the issue when the number of elements is even.

问题是我的算法只适用于奇数个元素。我很快写了这段代码，所以我很确定有更好的方法来实现我的想法以获得更好的性能，但我现在真的没有时间来优化它并解决问题元素是偶数。

It's one swap for every permutation and it uses a really simple way to know which elements to swap.

这是每个排列的一次交换，它使用一种非常简单的方法来知道要交换哪些元素。

I wrote an explanation of the method behind the code on my blog: http://antoinecomeau.blogspot.ca/2015/01/fast-generation-of-all-permutations.html

我在我的博客上写了对代码背后的方法的解释：http: //antoinecomeau.blogspot.ca/2015/01/fast-generation-of-all-permutations.html

回答by soultech

If you just want to calculate the number of possible permutations you can avoid all that hard work above and use something like this (contrived in c#):

如果您只想计算可能的排列数量，您可以避免上面的所有繁重工作并使用类似的东西（在 c# 中设计）：

public static class ContrivedUtils 
{
    public static Int64 Permutations(char[] array)
    {
        if (null == array || array.Length == 0) return 0;

        Int64 permutations = array.Length;

        for (var pos = permutations; pos > 1; pos--)
            permutations *= pos - 1;

        return permutations;
    }
}

You call it like this:

你这样称呼它：

var permutations = ContrivedUtils.Permutations("1234".ToCharArray());
// output is: 24
var permutations = ContrivedUtils.Permutations("123456789".ToCharArray());
// output is: 362880