cayleytable
Class PermutationGenerator

java.lang.Object
  extended by cayleytable.PermutationGenerator

public class PermutationGenerator
extends java.lang.Object

Class used to create permutations of a set of numbers from 0 to n-1

Author:
Michael Gilleland, Merriam Park Software { http://www.merriampark.com/perm.htm }

Field Summary
private  int[] a
          array of integers representing current permutation that is being sent back to requestor
private  java.math.BigInteger numLeft
          BigInteger of the number of permutations that have not been retrieved
private  java.math.BigInteger total
          BigInteger of the total number of permutations
 
Constructor Summary
PermutationGenerator(int n)
          Constructor to create the initial permutation of the list of integers from 0 to a given number.
 
Method Summary
private static java.math.BigInteger getFactorial(int n)
          Method to compute the factorial of a given integer
 int[] getNext()
          Method to generate next permutation (algorithm from Rosen p.
 java.math.BigInteger getNumLeft()
          Method to return number of permutations not yet generated
 java.math.BigInteger getTotal()
          Method to return total number of permutations
 boolean hasMore()
          Method to return whether any more permutations are left to use
 void reset()
          Method to reset the permutation list to the original array
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

a

private int[] a
array of integers representing current permutation that is being sent back to requestor


numLeft

private java.math.BigInteger numLeft
BigInteger of the number of permutations that have not been retrieved


total

private java.math.BigInteger total
BigInteger of the total number of permutations

Constructor Detail

PermutationGenerator

public PermutationGenerator(int n)
Constructor to create the initial permutation of the list of integers from 0 to a given number. 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.

Parameters:
n - integer size of the array to permutate
Method Detail

reset

public void reset()
Method to reset the permutation list to the original array


getNumLeft

public java.math.BigInteger getNumLeft()
Method to return number of permutations not yet generated

Returns:
BigInteger value of the number of permutations left

getTotal

public java.math.BigInteger getTotal()
Method to return total number of permutations

Returns:
BigInteger value of the total number of permutations

hasMore

public boolean hasMore()
Method to return whether any more permutations are left to use

Returns:
Boolean value determining if numLeft is greater than zero

getFactorial

private static java.math.BigInteger getFactorial(int n)
Method to compute the factorial of a given integer

Parameters:
n - integer to which compute the factorial
Returns:
BigInteger factorial of the given value

getNext

public int[] getNext()
Method to generate next permutation (algorithm from Rosen p. 284)

Returns:
integer array containing next permutation of list of integers from 0 to n-1