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 (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Permutations of an Array [ 1 2 ]    NEXT >
 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
 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.
 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 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 Thanks for advice. I've edited the post.
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply Why does my_next_permutation get exactly lexicographically next permutation from a given one? Let’s examine it intently. To generate the next permutation we should find such an element ai (with maximal possible i) that can be replaced by such an element aj that ai< aj and iI know that this works, but I am having a hard time understanding why this works. In other words, why does this procedure give us the next lexicographical permutation, rather than some other permutation?Also you can mention that next_permutation (at least the C implementation) ignores repeated permutations. So if you have repeated elements then 0,0,1,1 will go to 0,1,0,1 (instead of 0,0,1,1 again). This is a very useful feature that allows us to solve problems with long permutations (eg. length 20). For example see this solution, which did not time out on the challenge case.
 Re: Iterating Over All Permutations of an Array (response to post by dimkadimon) | Reply 1) For answer your question, crusial words in this paragraph are maximal and minimal. It generates exactly the next permutation (and not arbitrary lexicographically greater than given one) because of this.2) I mention it :-) Just re-read attentively.
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply 2) Ah I see now :)
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply Discussion“Objects supporting comparison” may be not only numbers, but characters, strings, etc. – any objects for those operation of comparison is defined.And there are some examples of getting next permutation:3 2 4 3 1 → 3 3 1 2 41 1 2 2 → 1 2 1 2And getting first permutation from the last one:5 4 3 2 1 → 1 2 3 4 5 Using these tricks, you may not only generate all permutations from the first one to the last one in increasing order. Of course, you may also generate them from the last one to the first one in decreasing order – you should just generate the last permutation by reversing the first one and write function my_prev_permutation, which should be a twin to my_next_permutation with operators >= comparing array elements turned into <=. You can also generate all permutations starting from and stopping at not only first or last, but any arbitrary one. But you should make sure of you really iterate over all permutations. In particular, when iterating from the first one to the last one it means that you should sort your array lexicographically beforehand. And if somebody in your room misses this point, it may be good time for you to challenge her solution quickly.But an interesting question may be: Why does my_next_permutation get exactly lexicographically next permutation from a given one? Let’s examine it intently. To generate the next permutation we should find such an element ai (with maximal possible i) that can be replaced by such an element aj that ai< aj and i (with minimal possible aj under these constraints), then swap ai and aj and reorder all elements with indices more than i non-decreasing.And our my_next_permutation does exactly this. First of all, we go from the last element to find the first such element that has greater right neighbor – and this is ai. We see that the sequence of elements with indices greater than i is ordered non-increasing. Then we find the minimal element with index j>i such that aj>ai and swap these two elements. Because old ai was greater than or equal to aj+1 (if j, of course), new sequence of elements with indices greater than i is still ordered non-increasing, so we should just reverse it to obtain non-decreasing sequence.Another question may be: What is the time complexity of algorithm? Answer is T(n)=A(n)*B(n), where T(n) is time complexity of whole algorithm of iterating all permutations, A(n) is an estimate of number of permutations, and B(n) is time complexity of getting next permutation. Of course, if we have an array with all elements distinct, A(n)=n!, and if there are k distinct groups of equal elements with size Si of i-th group, an answer should be n!/(S1!*…*Si!*…*Sk!). And B(n)=O(n), as we can see easily, because there are only three non-nested cycles in function my_next_permutation, and each of them run along the some part of array of length n. So if there are no equal elements in the array, time complexity of whole algorithm is O(n!*n).But, to be honest, that’s not the best asymptotical estimate for this algorithm. If we examine it more deeply, we recognize that two last elements are inspected at every iteration, but the third one – once per 2 times, the fourth one – once per 6 times, and so on. So the time complexity is O(n!+n!+n!/2+n!/6+n!/24+n!/120+...) = O(e*n!) = O(n!).Such an estimation of time complexity shows that this algorithm can be used only for small n, about 10 or 12. It is useful when you want to gather something information about every permutation and you can’t think of method giving this information without straightforward searching over all permutations. So our algorithm is some kind of brute force search. When there is a greater constraint on n, you should use something cleverer. On the other hand, if n is even lesser you can use even simpler recursive algorithm, in which at every recursion step (which is determined by current position, for which you choose an element to put in) you should iterate over all elements which haven’t been used in the prefix of the permutation and process the whole permutation every time you reach the last position.
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply As the instance of Nickolas I've supplemented "Discussion" section with new details and had to split initial post into two parts because of size limit.
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply So if there are no equal elements in the array, time complexity of whole algorithm is O(n!*n).That is not the whole truth. The next permutation algorithm always inspects two last elements, but the third one is inspected once per 2 times, the fourth one is inspected once per 6 times, the fifth one once per 24 times, etc. Thus, the time complexity is actuallyO(n!+n!+n!/2+n!/6+n!/24+n!/120+...) = O(e*n!) = O(n!)There is no swap function in Java, right? (Otherwise my_next_permutation should use it)
 Re: Iterating Over All Permutations of an Array (response to post by Eryx) | Reply Yes, it has been pointed already by it4.kp, but I think it isn't necessary to give the best asymptotical estimate in this case.I don't know about swap function: even coding this program in Java was rather hard for me. But as there are nobody who claims that there is one, I suppose there isn't :)
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply I think a short mention that next_permutation takes a constant amount of time on average would be more useful than the current simple analysis, because: everyone at this point should be able to do this simple calculation themselves, so it is not interesting (especially that it is naive), even if there is no direct practical importance in this case, I think it would be good for general educational purpose to note that some algorithms work much faster than one could get by just counting the nesting of loops, actually, what really matters in this case in TopCoder is not the time generating all permutations, but time of doing some stuff (X) for all of them. To do this, you obviously have to do the X thing N! times. So even if N is 8 and the X thing is something very complex, the "try all permutations" algorithm does not work.
 Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply As for the problem example, you can look at TheLuckyString. And this is Java solution where we do exactly what we say in previous paragraph – generate all permutations straightforward and check them for required property (no two adjacent elements are equal):```import java.util.*; public class TheLuckyString { 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 #include #include using namespace std; class TheLuckyString { public: int count (string a) { int i; int ans=0; sort(a.begin(),a.end()); reverse(a.begin(),a.end()); do { for (i=0; i #include #include using namespace std; class MatrixGame { vector ans; vector now; public: vector getMinimal (vector a) { int i,j; vector v; ans=now=a; for (i=0; i and permutate such pairs, or also create an array of indices.
 Re: Iterating Over All Permutations of an Array (response to post by Eryx) | Reply OK, as you insist, I added this estimation to the recipe (what made the post too big, so I splitted it).
 Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Permutations of an Array Previous Thread  |  Next Thread [ 1 2 ]    NEXT >