Generating permutations of a set (most efficiently)
|
4:21 AM |
No comments |
Generating permutations of a set (most efficiently)
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[] elements) where T : IComparable { // 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.
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.
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.
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).
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.
Thanks for reading everything! :)
Answer by Sani Singh Huttunen for Generating permutations of a set (most efficiently)
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; } Answer by Erez Robinson for Generating permutations of a set (most efficiently)
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.
Code:
public static IEnumerable> QuickPerm(this IEnumerable set) { int N = set.Count(); int[] a = new int[N]; int[] p = new int[N]; var yieldRet = new T[N]; List list = new List(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 by Colonel Panic for Generating permutations of a set (most efficiently)
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)
Skiena references D. Knuth. The Art of Computer Programming, Volume 4 Fascicle 2: Generating All Tuples and Permutations. Addison Wesley, 2005.
Answer by btilly for Generating permutations of a set (most efficiently)
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.
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.
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.
Answer by Mike Dunlavey for Generating permutations of a set (most efficiently)
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:
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; jAnswer by Sam for Generating permutations of a set (most efficiently)
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.
public class PermutationFinder { private T[] items; private Predicate SuccessFunc; private bool success = false; private int itemsCount; public void Evaluate(T[] items, Predicate 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().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 by SimpleVar for Generating permutations of a set (most efficiently)
Here is the fastest implementation I ended up with:
public class Permutations { private readonly Mutex _mutex = new Mutex(); private Action _action; private Action _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 action, bool async = false) { return this.Permutate(start, count, action, null, async); } public bool Permutate(int start, int count, Action actionUnsafe, bool async = false) { return this.Permutate(start, count, null, actionUnsafe, async); } private unsafe bool Permutate(int start, int count, Action action, Action 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)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:
- Permutations aren't lexicographic - this allows me to practically perform less operations between permutations.
- 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).
- 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.
- 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.
- 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).
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.
Answer by Antoine Comeau for Generating permutations of a set (most efficiently)
I created an algorithm slightly faster than Knuth's one:
11 elements:
mine: 0.39 seconds
Knuth's: 0.624 seconds
13 elements:
mine: 56.615 seconds
Knuth's: 98.681 seconds
Here's 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;iThe 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
Answer by soultech for Generating permutations of a set (most efficiently)
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; } } You call it like this:
var permutations = ContrivedUtils.Permutations("1234".ToCharArray()); // output is: 24 var permutations = ContrivedUtils.Permutations("123456789".ToCharArray()); // output is: 362880 Answer by Antonn Lejsek for Generating permutations of a set (most efficiently)
As there are many answers, I made some summary of that. 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 SimpleVars answer as it does not seem to work correct and is not safe. It was the fastest by a bit when there was no action, but with action on the permutation the speed decreased significantly. I optimized answer of @ErezRobinson a little to see the real performance of algorithm. It is the fastest one, too sad I have no idea how is works. Btw when I moved the summing (more later) into procedure to avoid calling of action, it got to 160ms.
public void QuickPermErez(IEnumerable set, Action 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 was summing the first item in array of every permutation to do basic test and to make it at least a bit real scenario. I altered the perm to be testable this way, but it was really cosmetic.
void perm(int[] s, int n, int i, Action 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 for completeness 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().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 by Eric Ouellet for Generating permutations of a set (most efficiently)
A little bit too late...
According to my tests, my implementation of Heap's algorithm seems to give fastest performance...
Performance test results for 12 items (12!) in 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
Advantages:
- 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 { /// /// 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 /// public static class Permutations { /// /// Heap's algorithm to find all pmermutations. Non recursive, more efficient. /// /// Items to permute in each possible ways /// /// Return true if cancelled public static bool ForAllPermutation(T[] items, Func 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; } /// /// 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 /// /// > GetPermutations(IEnumerable 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 })); } /// /// Swap 2 elements of same type /// /// (ref T a, ref T b) { T temp = a; a = b; b = temp; } /// /// Func to show how to call. It does a little test for an array of 4 items. /// 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; }); Answer by Ziezi for Generating permutations of a set (most efficiently)
Here is a recursive implementation with complexity O(n * n!)1 based on swapping of the elements of an array. The array is initialised 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]); } } } } On each recursive step we swap the last element with the current element pointed to by the local variable in the for loop and then we indicate the uniqueness of the swapping by: incrementing the local variable of the for loop and decrementing the termination condition of the for loop, which is initially set to the number of the elements in the array, when the latter becomes zero we terminate 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! permutations of n elements to be printed.
Answer by misiek for Generating permutations of a set (most efficiently)
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
Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72
0 comments:
Post a Comment