JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (oldest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Permutations of an Array << PREV    [ 1 2 ]
 Re: Iterating Over All Permutations of an Array (response to post by dimkadimon) | Reply Thanks for advice. I've edited the post.
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply You don't really need a picture. It would suffice to have your discussion relate to some examples of sequences. I was thinking something like this: http://wordaligned.org/articles/next-permutationBy the way, not all coders have access to reverse() method. Here is my Java implementation, which you are free to use:```//elements in a have to be sorted in ascending order //changes the elements to achieve the next permutation //returns false if there are no more permutations public static boolean nextPermutation(int[] a) { int N=a.length; int i=N-2; for (; i>=0; i--) if (a[i]=i; j--) { if (a[j]>a[i]) { int temp=a[i]; a[i]=a[j]; a[j]=temp; break; } } for (int j=i+1; j<(N+i+1)/2; j++) //reverse from a[i+1] to a[N-1] { int temp=a[j]; a[j]=a[N+i-j]; a[N+i-j]=temp; } return true; } ```
 Re: Iterating Over All Permutations of an Array (response to post by dimkadimon) | Reply You are right, maybe it would. I spent some time drawing the picture but couldn't insert it into the post :-(( I'll do it, if somebody explain to me how to use tag in this forum.
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply Good recipe. I think it would help the reader's understanding if the discussion gave some visual examples of sequences and their next permutations.
 Iterating Over All Permutations of an Array | Reply NameIterating Over All Permutations of an ArrayProblemYou have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.SolutionAssuming that quite natural order of permutations is lexicographic order, you should be able to do just three things:1) Generate the first permutation;2) Get the next permutation from a given one;3) Recognize the last permutation.And then you can use this simple algorithm (in pseudo-code):```array a[n]; generate_first_permutation(a); while (1) { // Do something with the array. if (is_last_permutation(a)) break; get_next_permutation(a); } ```Of course, as soon as the first permutation is just a lexicographically first, we can use for generating it well-known quick sort algorithm. Even more, in C++ STL there is nice function bool next_permutation (BidirectionalIterator first, BidirectionalIterator last) (and rather like this, the function named prev_permutation, if you want to iterate in reverse order). If the given permutation is not last, this function generates the next permutation and returns 1, else it generates the first permutation and returns 0. (Note that this function works correctly even if there are equal elements in the array.) Using all these, we can easily write our program in C++:```#include #include using namespace std; class Permutations { public: int howMany (vector a) { sort(a.begin(),a.end()); int ans=0; do { ++ans; } while (next_permutation(a.begin(),a.end())); return ans; } }; ```Done it, we can enjoy the life. But this is still a problem for coders who aren’t experiencing C++ language and thus have no such a great tool as STL. While sorting arrays is very common procedure for which we refer to other recipes, generating next permutation is not as well. So we should show how to write such a function manually. This code represents Java function bool my_next_permutation (int []), whose arguments are an array and number of permutating elements in it, and this function’s action copies C++ STL function’s one:```public boolean my_next_permutation(int[] a) { int n=a.length; int i,j,k,temp; i=n-2; while (i>=0 && a[i]>=a[i+1]) --i; if (i<0) { for (j=0,k=n-1; j=a[j]) --j; temp=a[i]; a[i]=a[j]; a[j]=temp; for (j=i+1,k=n-1; j
 Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Permutations of an Array Previous Thread  |  Next Thread << PREV    [ 1 2 ]