Permutations A

[JosAH]

Greetings,

last week I stated that a lot of topics in a lot of forums mention all sorts
of sorting problems. Last week's tip gave an answer to quite a bit of those
sorting problems. Another "favourite" (mind the quotes) topic is about
permutations and combinations. This week's tip shows how permutations can be
generated in an efficient way. A next tip talks about how combinations can
be generated efficiently.

First here's an extremely sloppy definition:

if a word S < T lexicographically then word S can be found before word T can
be found in a dictionary.

Here are all the words containing the three distinct characters A, B and C
in lexicographic order: ABC, ACB, BAC, BCA, CAB and CBA. Note that this is
the order in which they can be found in a dictionary (if the editors of that
dictionary considers them legitimate dictionary words at all.

The core of our algorithm attempts to find a next permutation given a current
permutation. The notion 'next' is defined as lexicographical ly next.

As an example consider the word ACEDB; what would the next permutation of this
word be? After a bit of fiddling you can figure out the next one: ADBCE

Here's how it's formally (pseudo code) done:

1) for a permutation p_0 p_1 ... p_n find the rightmost index value i such
that p_i < p_(i+1). If no such i can be found the current permutation is the
last permutation of them all; if so, stop.

For our example p_i would be the letter C because it's the rightmost letter
that happens to be less than the one to the right of it: C < E

2) find a rightmost index j such that p_j > p_i. Note that such a j can
always be found if step 1) succeeds.

For our example p_j would the letter D because it's the rightmost letter
that happens to be greater than p_i (D > C)

We count starting from zero (0) so i == 1 and j == 3.

3) Swap the elements p_i and p_j

For our example we swap the letters D and C and obtain: ADECB

4) reverse the postfix p_(i+1) ... p_n

For our example we reverse ECB and obtain ADBCE which happens to be the next
permutation of the current permutation ACEDB.

Note that we didn't need any recursion; just a bit of looping over indexes and
a bit of testing. Remember our Sortable interface from the previous Tip Of
The Week? Here it is again:

public interface Sortable {
	int length();
	int compare(int i, int j);
	void swap(int i, int j);
}

It looks like we can use that interface again, i.e. we need to compare
different things, we need to know the length of the permutation and we need
to be able to swap things. Note that we keep the notion of those 'things'
as vague as possible again.

Let's use this interface for our permutation algorithm. The four steps
of our pseudo code algorithm (see above) can easily be implemented as follows:

	public static Sortable permute(Sortable s) {
		
		int i, j;

		// step 1		
		for (i= s.length()-1; --i >= 0;)
			 if (s.compare(i, i+1) < 0)
				 break;
		
		if (i < 0) return null;

		// step 2		
		for (j= s.length(); --j > i;)
			if (s.compare(i, j) < 0)
				break;
		
		// step 3
		s.swap(i, j);
		
		// step 4
		for (j= s.length(); ++i < --j;)
			s.swap(i, j);
		
		return s;
	}

The comments just refer to the steps of the pseudo code algorithm. The method
above uses a Sortable for the generation of the next permutation (if any) and
doesn't really know *what* it is actually manipulating. The same advantages
as shown in the previous TOTW show up again: the algorithm couldn't care less
about what it's actually manipulating to construct a next permutation.

If no next permutation is present this method returns null, otherwise the
next permutation in the Sortable object is returned.

For your convenience, so you can copy and paste it directly to your private
bag of tricks again, here's the entire class definition. Note that the class
is just a utility class, i.e. it's not necessary to have a 'Permuter' object
around; the class doesn't have any state by itself and only has functionality.
Here's the complete class:

 
public final class Permute {
	
	private Permute() { }
	
	public static Sortable permute(Sortable s) {
		// code as above
	}
}

Note that this algorithm also works fine when a permutation contains duplicate
elements; e.g. for a first permutation AAB, the next permutations are produced:
ABA and BAA.

Here's a little class that exercises the above utility class:

public class MySortable implements Sortable {

	private String[] array;

	private MySortable(String array) { this.array= array; }

	public int length() {  // interface implementation

		return array.length;  
	}

	public int compare(int i, int j)  { // interface implementation

		return array[i].compareTo(array[j]); 
	}

	public void swap(int i, int j) { // interface implementation

		String t= array[i]; array[i= array[j]; array[j]= t;
	}

	public void print() {

		for (int i= 0; i < array.length; i++)
			System.out.print(array[i]+" ");
		System.out.println();
	}

	public static void main(String[] args) {

		MySortable s= new MySortable(new String[] {
						"Fred",
						"Pebbles",
						"Wilma" });
		do {
			s.print(s);
		} 
		while (s.permute() != null);
	}
}

In the next part of this Tip Of The Week we'll talk a bit about combinations.

kind regards,

Jos