combinatorics
Class CartesianProduct<T>

java.lang.Object
  combinatorics.CartesianProduct<T>

All Implemented Interfaces:

java.lang.Iterable<T[]>, java.util.Iterator<T[]>

public class CartesianProduct<T>
extends java.lang.Object
implements java.util.Iterator<T[]>, java.lang.Iterable<T[]>

A class that sequentially returns the cartesian product of sets, represented as a two-dimensional array. TODO: incorporate this into my CombinatoricOperator frame.

Author:

Hendrik Maryns

Field Summary

protected T[][]	elements The elements the operator works upon.
protected int[]	indices An integer array backing up the original one to keep track of the indices.

Constructor Summary

CartesianProduct(T[][] elements)
Initialise a new operator, with given elements and size of the arrays to be returned.

Method Summary

protected void	computeNext() Compute the next array of indices.
int	getNumLeft() Return number of variations not yet generated.
int	getTotal() Return the total number of variations.
boolean	hasNext() Returns true if the iteration has more elements.
protected void	initialiseIndices() Initialise the array of indices.
protected int	initialiseTotal() Compute the total number of elements to return.
java.util.Iterator<T[]>	iterator() A combinatoric operator is itself an iterator.
T[]	next() Compute the next combination.
void	remove() Not supported.
void	reset() Reset the iteration.

Methods inherited from class java.lang.Object

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

Field Detail

elements

protected T[][] elements

The elements the operator works upon.

indices

protected int[] indices

An integer array backing up the original one to keep track of the indices.

Constructor Detail

CartesianProduct

public CartesianProduct(T[][] elements)

Initialise a new operator, with given elements and size of the arrays to be returned.

Parameters:

elements - The elements on which this combinatoric operator has to act.

Method Detail

initialiseIndices

protected void initialiseIndices()

Initialise the array of indices. By default, it is initialised with incrementing integers.

initialiseTotal

protected int initialiseTotal()

Compute the total number of elements to return.

Parameters:

n - The number of elements the operator works on.

r - The size of the arrays to return.

Returns:

The total number of elements is always bigger than 0. | result >= 0

reset

public void reset()

Reset the iteration.

getNumLeft

public int getNumLeft()

Return number of variations not yet generated.

getTotal

public int getTotal()

Return the total number of variations.

Returns:

The factorial of the number of elements divided by the factorials of the size of the variations and the number of elements minus the size of the variations. That is, with the number of elements = n and the size of the variations = r: n^r

hasNext

public boolean hasNext()

Returns true if the iteration has more elements. This is the case if not all n! permutations have been covered.

Specified by:

hasNext in interface java.util.Iterator<T[]>

Returns:

The number of permutations to go is bigger than zero. | result == getNumLeft().compareTo(BigInteger.ZERO) > 0;

See Also:

Iterator.hasNext()

next

public T[] next()

Compute the next combination.

Specified by:

next in interface java.util.Iterator<T[]>

See Also:

Iterator.next()

computeNext

protected void computeNext()

Compute the next array of indices.

remove

public void remove()

Not supported.

Specified by:

remove in interface java.util.Iterator<T[]>

See Also:

Iterator.remove()

iterator

public java.util.Iterator<T[]> iterator()

A combinatoric operator is itself an iterator.

Specified by:

iterator in interface java.lang.Iterable<T[]>

Returns:

Itself. | result == this

See Also:

Iterable.iterator()