我想生成一个集合（一个集合）的所有排列，如下所示：
Collection: 1, 2, 3 Permutations: {1, 2, 3} {1, 3, 2} {2, 1, 3} {2, 3, 1} {3, 1, 2} {3, 2, 1}
通常，这不是“如何”的问题，而是更多关于如何最有效的问题。另外，我不想生成所有排列并返回它们，而是一次只生成一个排列，并且仅在必要时才继续（很像Iterators，我也曾尝试过，但结果却更少高效）。
我已经测试了许多算法和方法，并提出了这段代码，这是我尝试过的最有效的代码：
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; }
它的用法是发送一个元素数组，并返回一个布尔值，指示这是否是最后的字典排列，以及将该数组更改为下一个排列。
用法示例：
var arr = new[] {1, 2, 3}; PrintArray(arr); while (!NextPermutation(arr)) { PrintArray(arr); }
问题是我对代码的速度不满意。
迭代大小为11的数组的所有排列大约需要4秒钟。尽管可以认为它令人印象深刻，但是因为一组大小11的可能排列数量11!接近4000万。
11!
逻辑上，使用数组12的时间将12!是11! * 12，大约要花费12倍的时间，使用数组13的时间将比使用12的时间花费大约13倍的时间，依此类推。
12!
11! * 12
因此，您可以轻松了解如何使用大小为12及更大的数组来进行所有排列，这确实需要很长时间。
而且我有很强的直觉，可以以某种方式节省大量时间（无需切换到C＃以外的其他语言- 因为编译器优化确实确实可以很好地进行优化，并且我怀疑我是否可以在Assembly中手动进行优化）。
有谁知道其他方法可以更快地完成此任务？您是否有关于如何使当前算法更快的想法？
请注意，我不想使用外部库或服务来做到这一点-我想拥有代码本身，并且希望它尽可能地高效。
更新2018-05-28： 下面是另一个新的多线程版本（更快）。 * 也是有关置换的文章：置换：快速实现和允许多线程的新索引算法
更新2018-05-28：
有点晚了…
根据最近的测试（更新2018-05-22）
我的机器（millisecs）上发布的10个项目（10！）的性能测试结果：
我的计算机上发布的13个项目（13！）的性能测试结果（秒）：
我的解决方案的优势：
我对Heap算法的实现：
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"); } } }
这是我的测试代码：
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"); });
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; });
