combinatorics
Class CombinatoricOperator<T>

java.lang.Object
  combinatorics.CombinatoricOperator<T>

Type Parameters:

T - The type of the objects to operate on.

All Implemented Interfaces:

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

Direct Known Subclasses:

Combinator, Permuter, VariatorWithRepetition

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

A common superclass for all combinatoric operators. Makes use of the template method pattern to define all others.

Given an array of objects of type T, it returns all results of a certain combinatoric operation.

For efficiency, I changed this class to use ints for the counters. This means that e.g. for permutations, the maximal size of the array is about 20. If larger arrays are needed, BigInteger should be used (reintroduced). TODO: make simultaneous iteration possible.

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

protected

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

Method Summary

static <T> T[]	collectionToArray(java.util.Collection<T> coll, java.lang.Class<T> type) Return an array that contains all the elements of the given collection.
protected abstract void	computeNext() Compute the next array of indices.
static double	factorial(int n) Compute the factorial of n.
double	getNumLeft() Return number of variations not yet generated.
double	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 abstract double	initialiseTotal(int n, int r) 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

CombinatoricOperator

protected CombinatoricOperator(T[] elements,
                               int r)

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.

r - The size of the arrays to compute.

Method Detail

initialiseIndices

protected void initialiseIndices()

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

initialiseTotal

protected abstract double initialiseTotal(int n,
                                          int r)

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 double getNumLeft()

Return number of variations not yet generated.

Returns:

Return number of variations not yet generated.

getTotal

public double 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 n the number of elements and r the size of the variations: 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() > 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 abstract 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()

factorial

public static double factorial(int n)

Compute the factorial of n.

collectionToArray

public static <T> T[] collectionToArray(java.util.Collection<T> coll,
                                        java.lang.Class<T> type)

Return an array that contains all the elements of the given collection. Convenience method for clients of the class that have to transform collections.

Parameters:

coll - The collection to transform.

type - The type of the elements in the collection. Unfortunately, this method argument is necessary to create an array of the appropriate type. Blame Java generics.

Returns:

An array containing all elements of the collection. | for each element in result | coll.contains(element)