生成一组置换（最有效）
我想生成一个集合（集合）的所有排列，如下所示：
Collection: 1, 2, 3 Permutations: {1, 2, 3} {1, 3, 2} {2, 1, 3} {2, 3, 1} {3, 1, 2} {3, 2, 1} 一般来说，这不是一个“如何”的问题，而是关于如何最有效的问题。 另外，我不想生成所有的排列并返回它们，但是一次只产生一个排列，并且只在必要时才继续排列（就像迭代器一样 – 我也试过了，但是结果却less了有效）。
我已经testing了很多algorithm和方法，并提出了这个代码，这是我尝试过的最有效的代码：
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万。
从逻辑上看，12号的数组需要多出12倍的时间12! 是11! * 12 11! * 12 ，并且对于大小为13的数组，将比大小为12的时间多13倍，等等。
所以你可以很容易地理解如何使用12或更大的数组，要经过所有的排列真的需要很长的时间。
我有一个强烈的预感，我可以以某种方式削减那么多的时间（没有切换到C＃以外的语言 – 因为编译器优化真的非常好地优化，我怀疑我可以在Assembly中手动优化）。
有没有人知道任何其他方式来更快地完成？ 你有什么想法如何使目前的algorithm更快？
请注意，我不想使用外部库或服务来做到这一点 – 我想拥有代码本身，我希望它能像人类一样高效。
感谢您阅读所有内容！ 🙂
这可能是你在找什么。
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; }
那么，如果你能用C语言来处理，然后翻译成你所select的语言，那么你就不可能比这更快，因为时间将会被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);
我知道的最快的排列algorithm是QuickPermalgorithm。
这是实现，它使用yield return，所以你可以像需要的一样迭代一个。
码：
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) }
有点太晚了…
根据我的testing，我的堆algorithm的实现似乎给了最快的性能…
在我的机器上发布12个项目（12！）的性能testing结果：
- 1453051904 items in 10728 millisecs ==> My implementation of Heap (code included) - 1453051904 items in 18053 millisecs ==> Simple Plan - 1453051904 items in 85355 millisecs ==> Erez Robinson
优点：
- 堆的algorithm（每个置换单个交换）
- 没有乘法（就像在网上看到的一些实现）
- 内联交换
- 通用
- 没有不安全的代码
- 到位（非常低的内存使用）
- 不模（仅第一位比较）
我的堆实现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"); } } }
这是我的testing代码：
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; });
这是我结束的最快的实现：
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; } }
使用和testing性能：
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);
打印方法：
private static void PrintArr(int[] arr) { Console.WriteLine(string.Join(",", arr)); }
走得更深：
我甚至没有考虑这个问题，所以我只能解释我的代码，但总体思路是这样的：
- 排列不是词典 – 这使我实际上在排列之间执行更less的操作。
- 实现是recursion的，当“视图”大小为3时，它跳过复杂的逻辑，只是执行6次交换来获得6个排列（或者子排列，如果你愿意的话）。
- 因为排列不是按字典顺序排列的，我怎样才能决定把哪个元素带到当前“视图”（子排列）的开始？ 我logging在当前子排列recursion调用中已被用作“起始者”的元素，并简单地线性search未在我的数组尾部使用的元素。
- 该实现仅适用于整数，所以要对通用的元素集合进行置换，您只需使用Permutations类来排列索引，而不是实际的集合。
- 互斥体就是为了确保在asynchronous执行时不会搞错（注意，你可以传递一个UnsafeAction参数，这个参数将会得到一个指向置换数组的指针，你不能改变该数组中元素的顺序（指针）！如果你想，你应该复制数组到一个tmp数组，或者只是使用安全的行动参数，为你照顾 – 传递的数组已经是一个副本）。
注意：
我不知道这个实现真的有多好 – 我没有碰到这么长时间。 testing并与您自己的其他实现进行比较，如果您有任何反馈，请告诉我们！
请享用。
这是一个通用的排列查找器，它将遍历集合的每个排列并调用一个评估函数。 如果评估函数返回true（它find了正在查找的答案），那么排列查找器将停止处理。
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; } } } }
这是一个简单的实现：
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; } }
由于有很多答案，我对此做了一些总结。 对于11个项目：
OP original (NextPermutation) 363ms Sani Huttunen (NextPermutation) 334ms Mike Dunlavey (perm) 433ms Erez Robinson (QuickPerm) 210ms Sam (PermutationFinder) 608ms
我拒绝了SimpleVars的答案，因为它似乎不正确，不安全。 没有任何动作的时候速度最快，但在排列上的行动速度显着下降。 我优化了@ErezRobinson的答案，看一下algorithm的真实性能。 这是最快的，我也不知道如何工作。 顺便说一句，当我把这个总结（稍后）转移到程序中以避免行动时，它达到了160ms。
public void QuickPermErez<T>(IEnumerable<T> set, Action<T[]> action) { T[] arr = set.ToArray(); int N = arr.Length; int[] p = new int[N]; int i, j;// Upper Index i; Lower Index j T tmp; action(arr); i = 1; // setup first swap points to be 1 and 0 respectively (i & j) while (i < N) { if (p[i] < i) { j = (i & 1) * p[i]; // IF i is odd then j = p[i] otherwise j = 0 tmp = arr[j]; // swap(arr[j], arr[i]) arr[j] = arr[i]; arr[i] = tmp; action(arr); p[i]++; i = 1; } else // p[i] == i { p[i] = 0; // reset p[i] to zero i++; } } }
我正在总结每一个排列的第一个项目，做基本的testing，并且至less有一点真实的场景。 我改变了烫发可以这样testing，但它真的是美容。
void perm(int[] s, int n, int i, Action<int[]> ev) { if (i >= n - 1) ev(s); else { perm(s, n, i + 1, ev); for (int j = i + 1; j < n; j++) { //swap(s[i], s[j]); int tmp = s[i]; s[i] = s[j]; s[j] = tmp; perm(s, n, i + 1, ev); tmp = s[i]; s[i] = s[j]; s[j] = tmp; } } }
为了完整的testing代码：
int[] arr; int cnt; Stopwatch st = new Stopwatch(); int N = 11; arr = Enumerable.Range(1, N).ToArray(); cnt = 0; st.Restart(); do { cnt += arr[0]; } while (!NextPermutationOP(arr)); Console.WriteLine("OP: " + cnt + ", " + st.ElapsedMilliseconds.ToString()); arr = Enumerable.Range(1, N).ToArray(); cnt = 0; st.Restart(); do { cnt += arr[0]; } while (NextPermutationSani(arr)); Console.WriteLine("Sani: " + cnt + ", " + st.ElapsedMilliseconds.ToString()); arr = Enumerable.Range(1, N).ToArray(); cnt = 0; st.Restart(); new PermutationFinder<int>().Evaluate(arr, (x) => { cnt += x[0]; return false; }); Console.WriteLine("Sam: " + cnt + ", " + st.ElapsedMilliseconds.ToString()); arr = Enumerable.Range(1, N).ToArray(); cnt = 0; st.Restart(); perm(arr, N, 0, (x) => cnt += x[0]); Console.WriteLine("Mike: " + cnt + ", " + st.ElapsedMilliseconds.ToString()); arr = Enumerable.Range(1, N).ToArray(); cnt = 0; st.Restart(); QuickPermErez(arr, (x) => cnt += x[0]); Console.WriteLine("Erez: " + cnt + ", " + st.ElapsedMilliseconds.ToString());
这是一个基于交换数组元素的复杂度为O(n * n!) 1的recursion实现。 该数组的初始值为1, 2, ..., n 。
using System; namespace Exercise { class Permutations { static void Main(string[] args) { int setSize = 3; FindPermutations(setSize); } //----------------------------------------------------------------------------- /* Method: FindPermutations(n) */ private static void FindPermutations(int n) { int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = i + 1; } int iEnd = arr.Length - 1; Permute(arr, iEnd); } //----------------------------------------------------------------------------- /* Method: Permute(arr) */ private static void Permute(int[] arr, int iEnd) { if (iEnd == 0) { PrintArray(arr); return; } Permute(arr, iEnd - 1); for (int i = 0; i < iEnd; i++) { swap(ref arr[i], ref arr[iEnd]); Permute(arr, iEnd - 1); swap(ref arr[i], ref arr[iEnd]); } } } }
在每个recursion步骤中，我们将最后一个元素与for循环中局部variables所指向的当前元素进行交换，然后通过以下方式指示交换的唯一性：递增for循环的局部variables并递减for的终止条件循环，最初设置为数组元素的数量，当后者变为零时，我们终止recursion。
这里是辅助函数：
//----------------------------------------------------------------------------- /* Method: PrintArray() */ private static void PrintArray(int[] arr, string label = "") { Console.WriteLine(label); Console.Write("{"); for (int i = 0; i < arr.Length; i++) { Console.Write(arr[i]); if (i < arr.Length - 1) { Console.Write(", "); } } Console.WriteLine("}"); } //----------------------------------------------------------------------------- /* Method: swap(ref int a, ref int b) */ private static void swap(ref int a, ref int b) { int temp = a; a = b; b = temp; }
有n! 要打印的n元素的排列。
如果能find真正的数量级改进，我会感到惊讶。 如果有，那么C＃需要根本性的改进。 此外，对你的组合进行任何有趣的事情通常需要更多的工作，而不是产生它。 所以在整体scheme中，产生的成本是微不足道的。
这就是说，我会build议尝试以下的事情。 你已经尝试了迭代器。 但是你有没有尝试过把闭包当作input的函数，然后为每个find的排列调用闭包？ 根据C＃的内部机制，这可能会更快。
同样，你有尝试有一个函数返回一个闭包，将遍历一个特定的排列？
无论采用哪种方法，都可以进行一些微观优化。 例如，你可以对你的input数组进行sorting，然后你总是知道它的顺序。例如，你可以有一个布尔数组来指示这个元素是否小于下一个，而不是比较，你可以看看那个arrays。
在Steven Skiena algorithmdevise手册 （第二版14.4章）中有一个可访问的algorithm介绍和实现调查，
Skiena引用D. Knuth。 计算机编程的艺术，第4卷分册2：生成所有的元组和排列。 Addison卫斯理，2005年。
我创build了一个比Knuth更快的algorithm：
11个要素：
我的：0.39秒
Knuth：0.624秒
13个要素：
我的：56.615秒
Knuth的：98.681秒
这是我在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
As the author of this question was asking about an algorithm:
[…] generating a single permutation, at a time, and continuing only if necessary
I would suggest considering Steinhaus–Johnson–Trotter algorithm.
Steinhaus–Johnson–Trotter algorithm on Wikipedia
Beautifully explained here
It's 1 am and I was watching TV and thought of this same question, but with string values.
Given a word find all permutations. You can easily modify this to handle an array, sets, etc.
Took me a bit to work it out, but the solution I came up was this:
string word = "abcd"; List<string> combinations = new List<string>(); for(int i=0; i<word.Length; i++) { for (int j = 0; j < word.Length; j++) { if (i < j) combinations.Add(word[i] + word.Substring(j) + word.Substring(0, i) + word.Substring(i + 1, j - (i + 1))); else if (i > j) { if(i== word.Length -1) combinations.Add(word[i] + word.Substring(0, i)); else combinations.Add(word[i] + word.Substring(0, i) + word.Substring(i + 1)); } } }
Here's the same code as above, but with some comments
string word = "abcd"; List<string> combinations = new List<string>(); //i is the first letter of the new word combination for(int i=0; i<word.Length; i++) { for (int j = 0; j < word.Length; j++) { //add the first letter of the word, j is past i so we can get all the letters from j to the end //then add all the letters from the front to i, then skip over i (since we already added that as the beginning of the word) //and get the remaining letters from i+1 to right before j. if (i < j) combinations.Add(word[i] + word.Substring(j) + word.Substring(0, i) + word.Substring(i + 1, j - (i + 1))); else if (i > j) { //if we're at the very last word no need to get the letters after i if(i== word.Length -1) combinations.Add(word[i] + word.Substring(0, i)); //add i as the first letter of the word, then get all the letters up to i, skip i, and then add all the lettes after i else combinations.Add(word[i] + word.Substring(0, i) + word.Substring(i + 1)); } } }
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#):
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; } }
你这样称呼它：
var permutations = ContrivedUtils.Permutations("1234".ToCharArray()); // output is: 24 var permutations = ContrivedUtils.Permutations("123456789".ToCharArray()); // output is: 362880
