de.uni_tuebingen.sfb.lichtenstein.combinatorics
Class CartesianProduct<T>

java.lang.Object
  de.uni_tuebingen.sfb.lichtenstein.combinatorics.CartesianProduct<T>

Type Parameters:

T - The type of the elements one wants the cartesian product of.

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.
private int	numLeft The variations still to go.
private int	total The total number of variations to be computed.

Constructor Summary

CartesianProduct(T[][] elements)
Initialize 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.
private T[]	getResult(int[] indexes) Compute the result, based on the given array of indices.
int	getTotal() Return the total number of variations.
boolean	hasNext() Returns true if the iteration has more elements.
protected void	initializeIndices() Initialize the array of indices.
protected int	initializeTotal() 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.

numLeft

private int numLeft

The variations still to go.

total

private final int total

The total number of variations to be computed.

Constructor Detail

CartesianProduct

public CartesianProduct(T[][] elements)

Initialize 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.

Postcondition:

The total number of iterations is set to the product of the lengths of all subarrays.

| let sum =
       BigInteger.ONE
| for 0 <= i < elements.length | sum.multiply(elements[i].length) | new.getTotal() == sum

Postcondition:

The number of variations left is set to the total number.

| new.getNumLeft() == new.getTotal()

Method Detail

initializeIndices

protected void initializeIndices()

Initialize the array of indices. By default, it is initialized with incrementing integers.

initializeTotal

protected int initializeTotal()

Compute the total number of elements to return.

Returns:

The total number of elements is always bigger than 0.

| result >= 0

reset

public void reset()

Reset the iteration.

Postcondition:

The number of iterations to go is the same as the total number of iterations.

| new.getNumLeft() ==
       getTotal()

getNumLeft

public int getNumLeft()

Return number of variations not yet generated.

Returns:

The number of variations that can still be asked for.

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;

next

public T[] next()

Compute the next combination.

Specified by:

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

computeNext

protected void computeNext()

Compute the next array of indices.

getResult

private T[] getResult(int[] indexes)

Compute the result, based on the given array of indices.

Parameters:

indexes - An array of indices into the element array.

Returns:

An array consisting of the elements at positions of the given array.

| result[i] == elements[indexes[i]]

remove

public void remove()

Not supported.

Specified by:

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

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