cayleytable
Class PermutationGenerator

java.lang.Object
  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