ro.mosc.reco.algebra
Class PermutationGenerator

java.lang.Object
  ro.mosc.reco.algebra.PermutationGenerator

public class PermutationGenerator
extends java.lang.Object

The PermutationGenerator Java class systematically generates permutations. It relies on the fact that any set with n elements can be placed in one-to-one correspondence with the set {1, 2, 3, ..., n}. The algorithm is described by Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 282-284.

The class is very easy to use. Suppose that you wish to generate all permutations of the strings "a", "b", "c", and "d". Put them into an array. Keep calling the permutation generator's () method until there are no more permutations left. The () method returns an array of integers, which tell you the order in which to arrange your original array of strings. Here is a snippet of code which illustrates how to use the PermutationGenerator class.

 int[] indices;
 String[] elements = {"a", "b", "c", "d"};
 PermutationGenerator x = new PermutationGenerator (elements.length);
 StringBuffer permutation;
 while (x.hasMore ()) {
 permutation = new StringBuffer ();
 indices = x.getNext ();
 for (int i = 0; i < indices.length; i++) {
 permutation.append (elements[indices[i]]);
 }
 System.out.println (permutation.toString ());
 }
 

One caveat. Don't use this class on large sets. Recall that the number of permutations of a set containing n elements is n factorial, which is a very large number even when n is as small as 20. 20! is 2,432,902,008,176,640,000.

NOTE: This class was taken from the internet, as posted by Michael Gilleland on this website. The code was posted with the following comment: "The source code is free for you to use in whatever way you wish."

Field Summary

private int[]	a
private java.math.BigInteger	numLeft
private java.math.BigInteger	total

Constructor Summary

PermutationGenerator(int n)
Constructor.

Method Summary

private static java.math.BigInteger	getFactorial(int n) Compute factorial
int[]	getNext() Generate next permutation (algorithm from Rosen p.
java.math.BigInteger	getNumLeft() Return number of permutations not yet generated
java.math.BigInteger	getTotal() Return total number of permutations
boolean	hasMore() Are there more permutations?
void	reset() Reset

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

a

private int[] a

numLeft

private java.math.BigInteger numLeft

total

private java.math.BigInteger total

Constructor Detail

PermutationGenerator

public PermutationGenerator(int n)

Constructor. WARNING: Don't make n too large. Recall that the number of permutations is n! which can be very large, even when n is as small as 20 -- 20! = 2,432,902,008,176,640,000 and 21! is too big to fit into a Java long, which is why we use BigInteger instead.

Method Detail

reset

public void reset()

Reset

getNumLeft

public java.math.BigInteger getNumLeft()

Return number of permutations not yet generated

getTotal

public java.math.BigInteger getTotal()

Return total number of permutations

hasMore

public boolean hasMore()

Are there more permutations?

getFactorial

private static java.math.BigInteger getFactorial(int n)

Compute factorial

getNext

public int[] getNext()

Generate next permutation (algorithm from Rosen p. 284)