Creating set permutations (most efficient)

Question

I would like to generate all permutations of a collection (collection), for example:

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

This is not a question of how, in general, but more about how it is most effective. In addition, I would not want to generate all permutations and return them, but only generated a single permutation at a time and continued only if necessary (like the Iterators, which I also tried, but turned out to be less efficient).

I tested a lot of algorithms and approaches and came up with this code, which is the most effective of those that 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 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; } 

This usage will send an array of elements and return a boolean value indicating whether it was the last lexicographic permutation or not, as well as changing the array to the next permutation.

Usage example:

 var arr = new[] {1, 2, 3}; PrintArray(arr); while (!NextPermutation(arr)) { PrintArray(arr); } 

The thing is, 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 this can be considered impressive, since the number of possible permutations of the set of sizes 11 is 11! , which is about 40 million.

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

So, you can easily understand how using an array of 12 or more in size takes a lot of time to go through all the permutations.

And I have a strong hunch that I can somehow reduce the time (without switching to a language other than C #), because compiler optimizations really optimize quite nicely, and I doubt that I could optimize as well, manually, in Installation).

Does anyone know of any other way to do this faster? Do you have any ideas on how to run the current algorithm faster?

Please note that I do not want to use an external library or service for this - I want to have the code itself, and I want it to be as efficient as humanly possible.

Thank you for reading everything! :)

Answer 1

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

Use and 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); 

Printing method:

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

Go deeper:

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

• Permutations are not lexicographical - this allows me to practically perform fewer operations between permutations.
• The implementation is recursive, and when the size of the view is 3, it skips complex logic and simply performs 6 swaps to get 6 permutations (or sub permutations, if you want).
• Since the permutations are not in lexicographical order, how can I decide which element should be brought to the beginning of the current “representation” (sub permutation)? I keep a record of the elements that were already used as "starters" in the current recursive call with permutation and simply run linearly for one that was not used in the tail of my array.
• The implementation is for integers only, so to swap over a common set of elements, you simply use the Permutations class to swap indices instead of your actual collection.
• The mutex is only intended to ensure that everything does not hang when execution is asynchronous (note that you can pass the UnsafeAction parameter, which in turn will receive a pointer to a reconfigured array. You should not reorder the elements in this array (pointer )! If you want, you must copy the array to the tmp array or just use a safe action parameter that will take care of this for you - the passed array is already a copy).

Note:

I have no idea how good this implementation really is - I haven’t touched it for so long. Test and compare with other implementations yourself, and let me know if you have any feedback!

Enjoy.

Answer 2

This may be what you are 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; } 

Answer 3

Well, if you can handle this in C and then translate into your choice language, you cannot go much faster than this, because print will dominate in time:

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

Answer 4

The fastest permutation algorithm I know of is the QuickPerm algorithm.
Here is the implementation, it uses return returns so you can iterate as needed.

The 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) } 

Answer 5

A little late ...

According to my tests, my implementation of the heap algorithm seems to give maximum performance ...

Performance test results for 12 items (12!) In the release on my machine:

  - 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 

Benefits:

• Heap Algorithm (Single swap permutation)
• No multiplication (e.g., some implementations visible on the Internet)
• Built-in sharing
• Generic
• Insecure code
• In place (very low memory)
• No modulo (only comparison of the first bit)

My implementation is a heap 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 Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3 /// </summary> public static class Permutations { /// <summary> /// Heap 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 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 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 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"); } } } 

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

Examples of using:

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

Answer 6

Here is a general search for permutations that will iterate over each permutation of the collection and call the evalution function. If the evalution function returns true (she found the answer she was looking for), the permutation finder will stop processing.

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

Answer 7

As there are many answers, I made some summaries. For 11 items:

 OP original (NextPermutation) 363ms Sani Huttunen (NextPermutation) 334ms Mike Dunlavey (perm) 433ms Erez Robinson (QuickPerm) 210ms Sam (PermutationFinder) 608ms 

I rejected the answer of SimpleVars as it does not work correctly and is unsafe. It was the fastest when there was no action, but with the action on the permutation, the speed decreased significantly. I optimized @ErezRobinson's answer a bit to see the actual performance of the algorithm. This is the fastest, too sad, I have no idea how it works. Btw, when I moved the summation (later) to the procedure in order to avoid calling the action, it reached 160 ms.

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

I summarized the first element in the array of each permutation in order to run a basic test and make it at least a bit of a real script. I changed perm so that it could be tested this way, but it was really cosmetic.

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

And to complete the testing code:

 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()); 

Answer 8

Here is a recursive implementation with complexity O(n * n!) ¹ based on replacing array elements. The array is initialized with values ​​from 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]); } } } } 

At each recursive step, we replace the last element with the current element pointed to by the local variable in the for loop, and then specify the uniqueness of the swap: increasing the local variable of the for loop and decreasing the condition for ending the for loop, which is initially set to the number of elements in the array when the last equal to zero, we complete the recursion.

Here are the helper functions:

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

---

^{1. There are n! permutation of n elements for printing. A.}

Answer 9

There is an introduction to algorithms and an overview of implementations in the Steven Skiena Algorithm Development Guide (chapter 14.4 in the second edition)

Loken refers to D. Knut. The Art of Computer Programming, Volume 4. Fascicle 2: Generating All Tuples and Permutations. Addison Wesley, 2005.

Answer 10

I would be surprised if there really were corrections to the order. If there is, then C # needs a fundamental improvement. In addition, doing something interesting with your permutation usually requires more work than generating it. Thus, the cost of generation will be insignificant in the general scheme of things.

However, I suggest trying the following. You have already tried iterators. But have you tried a function that takes a closure as input and then calls that closure for every permutation found? Depending on the internal mechanics of C #, this can be faster.

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

With any approach, there are a number of micro-optimizations that you can experiment with. For example, you can sort your input array and after that you always know what order it is in. For example, you might have a bools array indicating whether this element is smaller than the next, and instead of comparing, you can just look at this array.

Answer 11

I created the algorithm a little faster than Knuth one:

11 elements:

mine: 0.39 seconds

Whip: 0.624 seconds

13 elements:

mine: 56.615 seconds

Whip: 98.681 seconds

Here is my code in 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]++; } } } 

, . , , , , , , .

, , .

: http://antoinecomeau.blogspot.ca/2015/01/fast-generation-of-all-permutations.html

Answer 12

:

[...],

Steinhaus-Johnson-Trotter.

Steinhaus-Johnson-Trotter

Answer 13

1 , , .

. , , ..

, , , :

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

---

, ,

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

Answer 14

, - ( #):

 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