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

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

Type Parameters:

T - The type of the elements of which combinations are to be returned.

All Implemented Interfaces:

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

public final class Combinator<T>
extends CombinatoricOperator<T>

A class that sequentially returns all combinations of a certain number out of an array of given elements. Thanks to Michael Gillegand for the base implementation: http://www.merriampark.com/comb.htm.

Author:

Hendrik Maryns

Field Summary

Fields inherited from class de.uni_tuebingen.sfb.lichtenstein.combinatorics.CombinatoricOperator

elements, indices

Constructor Summary

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

Method Summary

protected void	computeNext() Compute the next array of indices.
protected int	initializeTotal(int n, int r) Compute the total number of elements to return.

Methods inherited from class de.uni_tuebingen.sfb.lichtenstein.combinatorics.CombinatoricOperator

collectionToArray, factorial, getNumLeft, getTotal, hasNext, initializeIndices, iterator, next, remove, reset

Methods inherited from class java.lang.Object

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

Constructor Detail

Combinator

public Combinator(T[] elements,
                  int r)

Initialize a new Combinator, with given elements and size of the arrays to be returned.

Parameters:

elements - The elements of which combinations have to be computed.

r - The size of the combinations to compute.

Precondition:

r should not be greater than the length of the elements, and not smaller than 0.

| 0 <= r <= elements.length

Postcondition:

The total number of iterations is set to the factorial of the number of elements divided by the factorials of the size of the combinations and the number of elements minus the size of the combinations. That is, with the number of elements = n and the size of the combinations = r: n n! ( ) = --------- r (n-r)!r!

|
       new.getTotal() == factorial(elements.length).divide(
| factorial(r).multiply(factorial(elements.length-r))

Postcondition:

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

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

Method Detail

initializeTotal

protected int initializeTotal(int n,
                              int r)

Compute the total number of elements to return.

Specified by:

initializeTotal in class CombinatoricOperator<T>

Parameters:

n - The number of elements the operator works on.

r - The size of the arrays to return.

Returns:

The factorial of the number of elements divided by the factorials of the size of the combinations and the number of elements minus the size of the combinations. That is, with the number of elements = n and the size of the combinations = r: n n! ( ) = --------- r (n-r)!r!

computeNext

protected void computeNext()

Compute the next array of indices.

Specified by:

computeNext in class CombinatoricOperator<T>