JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Re: Iterating Over All Permutations of an Array Revision History (2 edits)
Re: Iterating Over All Permutations of an Array (response to post by Ferlon)
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 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<j> (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<n-1>, 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)
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 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<j (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<n-1, 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.
Re: Iterating Over All Permutations of an Array (response to post by Ferlon)
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 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<j (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<n-1, 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).

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 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<k; j++,k--) {
			temp=a[j];
			a[j]=a[k];
			a[k]=temp;
		}
		return false;
	}
	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;
	}
	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;
	}
};

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 next_permutation function as using it for generating all permutations of rows also, because it will result in total (8!)2 possibilities, what is too much to go into time limit; second, we cannot generate the next permutation of columns by generating next permutation of every row of the matrix simultaneously, since for distinct rows there may be distinct numbers of permutations of elements (because of equal elements in the same row) and even there are two rows with the same numbers of permutations, they may have distinct lexicographically numbers of initial permutations, and will not change equally under effect of next_permutation – so we should create a vector indicating current permutation of columns, and rearrange elements in the matrix after getting every next permutation of that vector’s elements. This is the solution:
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class MatrixGame {
vector<string> ans;
vector<string> now;
public:
	vector<string> getMinimal (vector<string> a) {
		int i,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()));
		return ans;
	}
};

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 ints into pair<int,int> and permutate such pairs, or also create an array of indices.