

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object ro.mosc.reco.algebra.PermutationGenerator
public class PermutationGenerator
The PermutationGenerator Java class systematically generates permutations. It relies on the fact that any set with n elements can be placed in onetoone correspondence with the set {1, 2, 3, ..., n}. The algorithm is described by Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGrawHill, 1991), pp. 282284.
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 

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

public PermutationGenerator(int n)
Method Detail 

public void reset()
public java.math.BigInteger getNumLeft()
public java.math.BigInteger getTotal()
public boolean hasMore()
private static java.math.BigInteger getFactorial(int n)
public int[] getNext()


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 