“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 4

1 1 2 2 → 1 2 1 2

And 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

But an interesting question may be: Why does

And our

Another question may be: What is the time complexity of algorithm? Answer is

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

Such an estimation of time complexity shows that this algorithm can be used only for small

If items of array are from very small set, for example chars 'A'..'Z' of digits '0'..'9', there is seem to be more simple to understand algorithm: first group all same items and then recursively populate resulting array from first index to last. Sample code below

staticvoidsub(int[] counters,char[] word,intp) {if(p == word.Length) Console.WriteLine(word);elsefor(inti = 0; i < 26; i++)if(counters[i] > 0) { counters[i]--; word[p] = (char)(i + (int)'A'); sub(counters, word, p + 1); counters[i]++; } }publicstaticvoidgenerate(strings) {int[] counters =newint[26];for(inti = 0; i < s.Length; i++) counters[s[i] - 'A']++;char[] word =newchar[s.Length]; sub(counters, word, 0); }staticvoidMain(string[] args) { generate("HELLO"); }

Point of harvesting our generated resuts is Console.WriteLine(word); it is somewrere deep inside recursion. If it is required to bring it to top just to make code more readable, c# users can use IEnumerable yield technique:

]]>staticIEnumerable<string> sub(int[] counters,char[] word,intp) {if(p == word.Length) yieldreturnnewstring(word);elsefor(inti = 0; i < 26; i++)if(counters[i] > 0) { counters[i]--; word[p] = (char)(i + (int)'A');foreach(stringwinsub(counters, word, p + 1)) yieldreturnw; counters[i]++; } }publicstaticIEnumerable<string> generate(strings) {int[] counters =newint[26];for(inti = 0; i < s.Length; i++) counters[s[i] - 'A']++;char[] word =newchar[s.Length];foreach(stringwinsub(counters, word, 0)) yieldreturnw; }staticvoidMain(string[] args) {foreach(stringwingenerate("HELLO")) Console.WriteLine(w); }

So more important than the implementation ( which is assumed know -next_permutation()- that this is called Algorithm L in Knuth's TAOCP 4: 7.2.1.2) it is the good use some criteria for pruning combinations (permutations) and at the end we obtain a reasonable running time.

Many problems use this kind of booby-trap to let the programmer to try to solve with a plenty quick solution which runs over all permutations (or combinations) that finish with a timeout or an unnecessary overhead as resources used (such us memory).]]>

importjava.util.*;publicclassTheLuckyString {publicbooleanmy_next_permutation(int[] a) {intn=a.length;inti,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<k; j++,k--) { temp=a[j]; a[j]=a[k]; a[k]=temp; }returnfalse; } j=n-1;while(a[i]>=a[j]) --j; temp=a[i]; a[i]=a[j]; a[j]=temp;for(j=i+1,k=n-1; j<k; j++,k--) { temp=a[j]; a[j]=a[k]; a[k]=temp; }returntrue; }publicintcount (Strings) {inta[]=newint[s.length()];inti;for(i=0; i<s.length(); ++i) a[i]=s.charAt(i); Arrays.sort(a);intans=0;do{for(i=0; i+1<a.length; ++i)if(a[i]==a[i+1])break;if(i+1==a.length) ans++; }while(my_next_permutation(a));returnans; } };

And this is more compact C++ solution, in which we will iterate from the last permutation to the first one – just to show that there are no major differences:

#include <vector> #include <string> #include <algorithm>usingnamespacestd;classTheLuckyString {public:intcount (stringa) {inti;intans=0; sort(a.begin(),a.end()); reverse(a.begin(),a.end());do{for(i=0; i<int(a.size())-1; ++i)if(a[i]==a[i+1])break;if(i==int(a.size())-1) ++ans; }while(prev_permutation(a.begin(),a.end()));returnans; } };

Another example may be MatrixGame. To solve it, we should search over all permutations of columns: got next permutation of columns, we sort obtained rows lexicographically and compare the whole matrix with current answer. There are two thin details: first, we should not so take a fancy of

#include <string> #include <vector> #include <algorithm>usingnamespacestd;classMatrixGame { vector<string> ans; vector<string> now;public: vector<string> getMinimal (vector<string> a) {inti,j; vector<int> v; ans=now=a;for(i=0; i<a[0].size(); ++i) v.push_back(i);do{for(i=0; i<a.size(); ++i)for(j=0; j<a[i].size(); ++j) now[i][j]=a[i][v[j]]; sort(now.begin(),now.end());if(now<ans) ans=now; }while(next_permutation(v.begin(),v.end()));returnans; } };

And the last example will be TheMoviesLevelTwoDivTwo. Here we should iterate over all possible permutations of movies and punctually simulate John’s scare level during watching them. As every movie has two parameters – length and scary moment – we can join these two

]]>

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 :)]]>