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

java.lang.Object
  extended by de.uni_tuebingen.sfb.lichtenstein.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.
private  int numLeft
          The variations still to go.
private  int total
          The total number of variations to be computed.
 
Constructor Summary
protected CombinatoricOperator(T[] elements, int r)
          Initialize 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 int factorial(int n)
          Compute the factorial of n.
 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 abstract  int initializeTotal(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.


numLeft

private int numLeft
The variations still to go.


total

private final int total
The total number of variations to be computed.

Constructor Detail

CombinatoricOperator

protected CombinatoricOperator(T[] elements,
                               int r)
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.
r - The size of the arrays to compute.
Precondition:
r should not be smaller than 0.
| 0 <= r
Postcondition:
The total number of iterations is set to the correct number.
| new.getTotal() == initializeTotal();
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 abstract int initializeTotal(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.

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 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;

next

public T[] next()
Compute the next combination.

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

computeNext

protected abstract 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

factorial

public static int factorial(int n)
Compute the factorial of n.

Parameters:
n - The number of which the factorial is to be computed. Should be less than 20, otherwise integer overflow occurs.
Returns:
The factorial of n, <code>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.

Type Parameters:
T - The type of the elements of the collection.
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)