JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Iterating Over All Permutations of an Array | Reply
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 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 <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=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;
}
Subject Author Date
Iterating Over All Permutations of an Array Ferlon Jul 19, 2010 at 5:34 PM EDT
Re: Iterating Over All Permutations of an Array dimkadimon Jul 19, 2010 at 10:02 PM EDT
Re: Iterating Over All Permutations of an Array Ferlon Jul 20, 2010 at 1:58 AM EDT
Re: Iterating Over All Permutations of an Array dimkadimon Jul 20, 2010 at 8:45 AM EDT
Re: Iterating Over All Permutations of an Array Ferlon Jul 20, 2010 at 1:56 PM EDT
Re: Iterating Over All Permutations of an Array dimkadimon Jul 20, 2010 at 8:59 PM EDT
Re: Iterating Over All Permutations of an Array Ferlon Jul 20, 2010 at 9:27 PM EDT
Re: Iterating Over All Permutations of an Array dimkadimon Jul 20, 2010 at 10:14 PM EDT
Re: Iterating Over All Permutations of an Array Ferlon Aug 15, 2010 at 7:50 AM EDT
Re: Iterating Over All Permutations of an Array Ferlon Aug 15, 2010 at 7:55 AM EDT
Re: Iterating Over All Permutations of an Array Eryx Nov 4, 2010 at 5:47 PM EDT
Re: Iterating Over All Permutations of an Array Ferlon Nov 5, 2010 at 11:54 AM EDT
Re: Iterating Over All Permutations of an Array Eryx Nov 5, 2010 at 2:39 PM EDT
Re: Iterating Over All Permutations of an Array Ferlon Nov 5, 2010 at 3:49 PM EDT
Re: Iterating Over All Permutations of an Array Ferlon Nov 5, 2010 at 3:46 PM EDT
Re: Iterating Over All Permutations of an Array devwebcl Dec 22, 2010 at 2:09 PM EST
Re: Iterating Over All Permutations of an Array Ferlon Dec 22, 2010 at 2:38 PM EST
Re: Iterating Over All Permutations of an Array Nickolas Dec 22, 2010 at 3:03 PM EST
Re: Iterating Over All Permutations of an Array NKolotey Dec 23, 2010 at 12:51 AM EST
Re: Iterating Over All Permutations of an Array Ferlon Jan 6, 2011 at 4:39 PM EST
RSS