

Revision History 

Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <vector>
#include <algorithm>
using namespace std;
class Permutations {
public:
int howMany (vector<int> 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=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
for (j=0,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return false;
}
j=n1;
while (a[i]>=a[j]) j;
temp=a[i];
a[i]=a[j];
a[j]=temp;
for (j=i+1,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return true;
}


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <vector>
#include <algorithm>
using namespace std;
class Permutations {
public:
int howMany (vector<int> 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=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
for (j=0,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return false;
}
j=n1;
while (a[i]>=a[j]) j;
temp=a[i];
a[i]=a[j];
a[j]=temp;
for (j=i+1,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return true;
}
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 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 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 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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only three nonnested 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).
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.
As for the problem example, you can look at TheLuckyString. And this is Java solution:
import java.util.*;
public class TheLuckyString {
public boolean my_next_permutation(int[] a) {
int n=a.length;
int i,j,k,temp;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
for (j=0,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return false;
}
j=n1;
while (a[i]>=a[j]) j;
temp=a[i];
a[i]=a[j];
a[j]=temp;
for (j=i+1,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return true;
}
public int count (String s) {
int a[]=new int[s.length()];
int i;
for (i=0; i<s.length(); ++i) a[i]=s.charAt(i);
Arrays.sort(a);
int ans=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));
return ans;
}
};
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>
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<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()));
return ans;
}
};


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <vector>
#include <algorithm>
using namespace std;
class Permutations {
public:
int howMany (vector<int> 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=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
for (j=0,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return false;
}
j=n1;
while (a[i]>=a[j]) j;
temp=a[i];
a[i]=a[j];
a[j]=temp;
for (j=i+1,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return true;
}
Discussion “Objects supporting comparison” may be not only numbers, but characters, strings, vectors, 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 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 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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only three nonnested 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).
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.
As for the problem example, you can look at TheLuckyString. And this is Java solution:
import java.util.*;
public class TheLuckyString {
public boolean my_next_permutation(int[] a) {
int n=a.length;
int i,j,k,temp;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
for (j=0,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return false;
}
j=n1;
while (a[i]>=a[j]) j;
temp=a[i];
a[i]=a[j];
a[j]=temp;
for (j=i+1,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return true;
}
public int count (String s) {
int a[]=new int[s.length()];
int i;
for (i=0; i<s.length(); ++i) a[i]=s.charAt(i);
Arrays.sort(a);
int ans=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));
return ans;
}
};
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>
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<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()));
return ans;
}
};


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <vector>
#include <algorithm>
using namespace std;
class Permutations {
public:
int howMany (vector<int> 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=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
for (j=0,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return false;
}
j=n1;
while (a[i]>=a[j]) j;
temp=a[i];
a[i]=a[j];
a[j]=temp;
for (j=i+1,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return true;
}
Discussion “Objects supporting comparison” may be not only numbers, but characters, strings, vectors, 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 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 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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only two nonnested 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).
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.
As for the problem example, you can look at TheLuckyString. And this is Java solution:
import java.util.*;
public class TheLuckyString {
public boolean my_next_permutation(int[] a) {
int n=a.length;
int i,j,k,temp;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
for (j=0,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return false;
}
j=n1;
while (a[i]>=a[j]) j;
temp=a[i];
a[i]=a[j];
a[j]=temp;
for (j=i+1,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return true;
}
public int count (String s) {
int a[]=new int[s.length()];
int i;
for (i=0; i<s.length(); ++i) a[i]=s.charAt(i);
Arrays.sort(a);
int ans=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));
return ans;
}
};
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>
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<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()));
return ans;
}
};


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <vector>
#include <algorithm>
using namespace std;
class Permutations {
public:
int howMany (vector<int> a) {
sort(a.begin(),a.end());
int ans=0;
do {
++ans;
} while (next_permutation(a.begin(),a.end()));
}
};
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=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
for (j=0,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return false;
}
j=n1;
while (a[i]>=a[j]) j;
temp=a[i];
a[i]=a[j];
a[j]=temp;
for (j=i+1,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return true;
}
Discussion “Objects supporting comparison” may be not only numbers, but characters, strings, vectors, 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 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 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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only two nonnested 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).
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.
As for the problem example, you can look at TheLuckyString. And this is Java solution:
import java.util.*;
public class TheLuckyString {
public boolean my_next_permutation(int[] a) {
int n=a.length;
int i,j,k,temp;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
for (j=0,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return false;
}
j=n1;
while (a[i]>=a[j]) j;
temp=a[i];
a[i]=a[j];
a[j]=temp;
for (j=i+1,k=n1; j<k; j++,k) {
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
return true;
}
public int count (String s) {
int a[]=new int[s.length()];
int i;
for (i=0; i<s.length(); ++i) a[i]=s.charAt(i);
Arrays.sort(a);
int ans=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));
return ans;
}
};
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>
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<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()));
return ans;
}
};


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <algorithm>
#include <cstring>
using namespace std;
const int c=100;
int n;
int a[c];
int main() {
scanf("%d",&n);
int i;
for (i=0; i<n; ++i) scanf("%d",&a[i]);
sort(a,a+n);
do {
for (i=0; i<n; ++i) printf("%d ",a[i]);
printf("\n");
} while (next_permutation(a,a+n));
return 0;
}
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 function bool my_next_permutation (int *, int), whose arguments are an array and number of permutating elements in it, and this function’s action copies STL function’s one:
bool my_next_permutation (int *a, int n) {
int i,j;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
reverse(a,a+n);
return 0;
}
j=n1;
while (a[i]>=a[j]) j;
swap(a[i],a[j]);
reverse(a+i+1,a+n);
return 1;
}
Discussion 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 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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only two nonnested 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).
As for the problem example, you can look at TheLuckyString.


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <algorithm>
#include <cstring>
using namespace std;
const int c=100;
int n;
int a[c];
int main() {
scanf("%d",&n);
int i;
for (i=0; i<n; ++i) scanf("%d",&a[i]);
sort(a,a+n);
do {
for (i=0; i<n; ++i) printf("%d ",a[i]);
printf("\n");
} while (next_permutation(a,a+n));
return 0;
}
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 function bool my_next_permutation (int *, int), whose arguments are an array and number of permutating elements in it, and this function’s action copies STL function’s one:
bool my_next_permutation (int *a, int n) {
int i,j;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
reverse(a,a+n);
return 0;
}
j=n1;
while (a[i]>=a[j]) j;
swap(a[i],a[j]);
reverse(a+i+1,a+n);
return 1;
}
Discussion 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 all operators >= turned into <=. You can also generate all permutations starting from and stopping at not only first or last, but any arbitrary one.
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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only two nonnested 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).
As for the problem example, you can look at TheLuckyString.


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <algorithm>
#include <cstring>
using namespace std;
const int c=100;
int n;
int a[c];
int main() {
scanf("%d",&n);
int i;
for (i=0; i<n; ++i) scanf("%d",&a[i]);
sort(a,a+n);
do {
for (i=0; i<n; ++i) printf("%d ",a[i]);
printf("\n");
} while (next_permutation(a,a+n));
return 0;
}
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 function bool my_next_permutation (int *, int), whose arguments are an array and number of permutating elements in it, and this function’s action copies STL function’s one:
bool my_next_permutation (int *a, int n) {
int i,j;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
reverse(a,a+n);
return 0;
}
j=n1;
while (a[i]>=a[j]) j;
swap(a[i],a[j]);
reverse(a+i+1,a+n);
return 1;
}
Discussion A picture below may help to understand how next permutation is generated from the current one: <img src=”https://docs.google.com/leaf?id=0B7YZDDYgN67VNDZkNTkxMWEtZDFlNS00YTg3LTljZDMtNTY1NWM3MDdmN2Jj&hl=en”>
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 all operators >= turned into <=. You can also generate all permutations starting from and stopping at not only first or last, but any arbitrary one.
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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only two nonnested 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).
As for the problem example, you can look at TheLuckyString.


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <algorithm>
#include <cstring>
using namespace std;
const int c=100;
int n;
int a[c];
int main() {
scanf("%d",&n);
int i;
for (i=0; i<n; ++i) scanf("%d",&a[i]);
sort(a,a+n);
do {
for (i=0; i<n; ++i) printf("%d ",a[i]);
printf("\n");
} while (next_permutation(a,a+n));
return 0;
}
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 function bool my_next_permutation (int *, int), whose arguments are an array and number of permutating elements in it, and this function’s action copies STL function’s one:
bool my_next_permutation (int *a, int n) {
int i,j;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
reverse(a,a+n);
return 0;
}
j=n1;
while (a[i]>=a[j]) j;
swap(a[i],a[j]);
reverse(a+i+1,a+n);
return 1;
}
Discussion A picture below may help to understand how next permutation is generated from the current one: <img src="https://docs.google.com/leaf?id=0B7YZDDYgN67VNDZkNTkxMWEtZDFlNS00YTg3LTljZDMtNTY1NWM3MDdmN2Jj&hl=en">
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 all operators >= turned into <=. You can also generate all permutations starting from and stopping at not only first or last, but any arbitrary one.
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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only two nonnested 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).
As for the problem example, you can look at TheLuckyString.


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <algorithm>
#include <cstring>
using namespace std;
const int c=100;
int n;
int a[c];
int main() {
scanf("%d",&n);
int i;
for (i=0; i<n; ++i) scanf("%d",&a[i]);
sort(a,a+n);
do {
for (i=0; i<n; ++i) printf("%d ",a[i]);
printf("\n");
} while (next_permutation(a,a+n));
return 0;
}
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 function bool my_next_permutation (int *, int), whose arguments are an array and number of permutating elements in it, and this function’s action copies STL function’s one:
bool my_next_permutation (int *a, int n) {
int i,j;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
reverse(a,a+n);
return 0;
}
j=n1;
while (a[i]>=a[j]) j;
swap(a[i],a[j]);
reverse(a+i+1,a+n);
return 1;
}
Discussion 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 all operators >= turned into <=. You can also generate all permutations starting from and stopping at not only first or last, but any arbitrary one.
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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only two nonnested 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).
As for the problem example, you can look at TheLuckyString.


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <algorithm>
#include <cstring>
using namespace std;
const int c=100;
int n;
int a[c];
int main() {
scanf("%d",&n);
int i;
for (i=0; i<n; ++i) scanf("%d",&a[i]);
sort(a,a+n);
do {
for (i=0; i<n; ++i) printf("%d ",a[i]);
printf("\n");
} while (next_permutation(a,a+n));
return 0;
}
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 function bool my_next_permutation (int *, int), whose arguments are an array and number of permutating elements in it, and this function’s action copies STL function’s one:
bool my_next_permutation (int *a, int n) {
int i,j;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
reverse(a,a+n);
return 0;
}
j=n1;
while (a[i]>=a[j]) j;
swap(a[i],a[j]);
reverse(a+i+1,a+n);
return 1;
}
Discussion 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 all operators >= turned into <=. You can also generate all permutations starting from and stopping at not only first or last, but any arbitrary one.
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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only two nonnested 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).
As for the problem example, you can look at TheLuckyString.


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <algorithm>
#include <cstring>
using namespace std;
const int c=100;
int n;
int a[c];
int main() {
scanf("%d",&n);
int i;
for (i=0; i<n; ++i) scanf("%d",&a[i]);
sort(a,a+n);
do {
for (i=0; i<n; ++i) printf("%d ",a[i]);
printf("\n");
} while (next_permutation(a,a+n));
return 0;
}
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 function bool my_next_permutation (int *, int), whose arguments are an array and number of permutating elements in it, and this function’s action copies STL function’s one:
bool my_next_permutation (int *a, int n) {
int i,j;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
reverse(a,a+n);
return 0;
}
j=n1;
while (a[i]>=a[j]) j;
swap(a[i],a[j]);
reverse(a+i+1,a+n);
return 1;
}
Discussion 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 all operators >= turned into <=. You can also generate all permutations starting from and stopping at not only first or last, but any arbitrary one.
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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j> (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1>, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}!*…*S_{i}!*…*S_{k}!). And B(n)=O(n), as we can see easily, because there are only two nonnested 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).
As for the problem example, you can look at TheLuckyString.


Name Iterating Over All Permutations of an Array
Problem You have an array of objects supporting comparison, and you want to iterate through all possible permutations of these objects.
Solution Assuming 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 pseudocode):
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 wellknown 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 <algorithm>
#include <cstring>
using namespace std;
const int c=100;
int n;
int a[c];
int main() {
scanf("%d",&n);
int i;
for (i=0; i<n; ++i) scanf("%d",&a[i]);
sort(a,a+n);
do {
for (i=0; i<n; ++i) printf("%d ",a[i]);
printf("\n");
} while (next_permutation(a,a+n));
return 0;
}
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 function bool my_next_permutation (int *, int), whose arguments are an array and number of permutating elements in it, and this function’s action copies STL function’s one:
bool my_next_permutation (int *a, int n) {
int i,j;
i=n2;
while (i>=0 && a[i]>=a[i+1]) i;
if (i<0) {
reverse(a,a+n);
return 0;
}
j=n1;
while (a[i]>=a[j]) j;
swap(a[i],a[j]);
reverse(a+i+1,a+n);
return 1;
}
Discussion 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 all operators >= turned into <=. You can also generate all permutations starting from and stopping at not only first or last, but any arbitrary one.
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 a_{i} (with maximal possible i) that can be replaced by such an element a_{j} that a_{i}< a_{j} and i<j (with minimal possible a_{j} under these constraints), then swap a_{i} and a_{j} and reorder all elements with indices more than i nondecreasing. 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 a_{i}. We see that the sequence of elements with indices greater than i is ordered nonincreasing. Then we find the minimal element with index j>i such that a_{j}>a_{i} and swap these two elements. Because old a_{i} was greater than or equal to a_{j+1} (if j<n1, of course), new sequence of elements with indices greater than i is still ordered nonincreasing, so we should just reverse it to obtain nondecreasing 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 S_{i} of ith group, an answer should be n!/(S_{1}*…*S_{i}*…*S_{k}). And B(n)=O(n), as we can see easily, because there are only two nonnested 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).
As for the problem example, you can look at TheLuckyString.

