Top Description Fields Constructors Methods
groovy.util

public Class PermutationGenerator<E>

extends Object
implements Iterator<List<E>>
Class Inheritance
All Implemented Interfaces
java.util.Iterator
Imports
org.codehaus.groovy.runtime.DefaultGroovyMethods, java.math.BigInteger, java.util.ArrayList, .Collection, .Iterator, .List
Systematically generate permutations. Adapted from Java Code by Michael Gilleland (released with no restrictions) using an algorithm described here: Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 282-284

Field Summary

Modifier and TypeField and Description
private final int[]
a

private final List<E>
items

private BigInteger
numLeft

private final BigInteger
total

Constructor Summary

AccessConstructor and Description
public
PermutationGenerator(Collection<E>
the items to permute
items)

Warning

Don't make n too large.

public
PermutationGenerator(Iterable<E> items)

Method Summary

Modifier and TypeMethod and Description
private static BigInteger

Returns:

the factorial for n
getFactorial(int
the input integer
n)

Compute factorial (TODO: expose this)

public BigInteger
getTotal()

public boolean
hasNext()

Implements java.util.Iterator.hasNext.

Returns true if the iteration has more elements.
public List<E>

Returns:

the items permuted
next()

Implements java.util.Iterator.next.

Generate next permutation (algorithm from Rosen p.
public void
remove()

Overrides default java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation).
public void
reset()

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

aback to summary
private final int[] a
itemsback to summary
private final List<E> items
numLeftback to summary
private BigInteger numLeft
totalback to summary
private final BigInteger total

Constructor Detail

PermutationGeneratorback to summary
public PermutationGenerator(Collection<E> items)

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
items:Collection<E>

the items to permute

PermutationGeneratorback to summary
public PermutationGenerator(Iterable<E> items)

Method Detail

getFactorialback to summary
private static BigInteger getFactorial(int n)

Compute factorial (TODO: expose this)

Parameters
n:int

the input integer

Returns:BigInteger

the factorial for n

getTotalback to summary
public BigInteger getTotal()
hasNextback to summary
public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

Returns:boolean

true if the iteration has more elements

nextback to summary
public List<E> next()

Implements java.util.Iterator.next.

Generate next permutation (algorithm from Rosen p. 284)

Returns:List<E>

the items permuted

removeback to summary
public void remove()

Overrides default java.util.Iterator.remove.

Doc from java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next.

The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method, unless an overriding class has specified a concurrent modification policy.

The behavior of an iterator is unspecified if this method is called after a call to the forEachRemaining method.

resetback to summary
public void reset()