package de.uni_tuebingen.sfb.macke.utilities;
import static java.math.BigInteger.ONE;
import static java.math.BigInteger.ZERO;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.Iterator;
/**
* A common superclass for all combinatoric operators. Makes use of the
* template method pattern to define all others.
*
* @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
*/
public abstract class CombinatoricOperator<T> implements Iterator<T[]>,
Iterable<T[]> {
/**
* Initialise a new operator, with given elements and size of the arrays
* to be returned.
*
* @param elements
* The elements on which this combinatoric operator has to act.
* @param r
* The size of the arrays to compute.
* @pre r should not be smaller than 0.
* | 0 <= r
* @post The total number of iterations is set to the correct number.
* | new.getTotal() == initialiseTotal();
* @post The number of variations left is set to the total number.
* | new.getNumLeft() == new.getTotal()
*/
protected CombinatoricOperator(T[] elements, int r) {
assert 0 <= r;
indices = new int[r];
this.elements = elements.clone();
total = initialiseTotal(elements.length, r);
reset();
}
/**
* The elements the operator works upon.
*/
protected T[] elements;
/**
* An integer array backing up the original one to keep track of the
* indices.
*/
protected int[] indices;
/**
* Initialise the array of indices. By default, it is initialised with
* incrementing integers.
*/
protected void initialiseIndices() {
for (int i = 0; i < indices.length; i++) {
indices[i] = i;
}
}
/**
* The variations still to go.
*/
private BigInteger numLeft;
/**
* The total number of variations to be computed.
*/
private BigInteger total;
/**
* Compute the total number of elements to return.
*
* @param n
* The number of elements the operator works on.
* @param r
* The size of the arrays to return.
* @return The total number of elements is always bigger than 0.
* | result >= 0
*/
protected abstract BigInteger initialiseTotal(int n, int r);
/**
* Reset the iteration.
*
* @post The number of iterations to go is the same as the total number
* of iterations.
* | new.getNumLeft() == getTotal()
*/
public void reset() {
initialiseIndices();
numLeft = total;
}
/**
* Return number of variations not yet generated.
*/
public BigInteger getNumLeft() {
return numLeft;
}
/**
* Return the total number of variations.
*
* @return 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
*/
public BigInteger getTotal() {
return total;
}
/**
* Returns <tt>true</tt> if the iteration has more elements. This is the
* case if not all n! permutations have been covered.
*
* @return The number of permutations to go is bigger than zero.
* | result == getNumLeft().compareTo(BigInteger.ZERO) > 0;
* @see java.util.Iterator#hasNext()
*/
public boolean hasNext() {
return numLeft.compareTo(ZERO) == 1;
}
/**
* Compute the next combination.
*
* @see java.util.Iterator#next()
*/
public T[] next() {
if (!numLeft.equals(total)) {
computeNext();
}
numLeft = numLeft.subtract(ONE);
return getResult(indices);
}
/**
* Compute the next array of indices.
*/
protected abstract void computeNext();
/**
* Compute the result, based on the given array of indices.
*
* @param indexes
* An array of indices into the element array.
* @return An array consisting of the elements at positions of the given
* array.
* | result[i] == elements[indexes[i]]
*/
@SuppressWarnings("unchecked")
private T[] getResult(int[] indexes) {
T[] result = (T[]) Array.newInstance(elements.getClass()
.getComponentType(), indexes.length);
for (int i = 0; i < result.length; i++) {
result[i] = elements[indexes[i]];
}
return result;
}
/**
* Not supported.
*
* @see java.util.Iterator#remove()
*/
public void remove() {
throw new UnsupportedOperationException();
}
/**
* A combinatoric operator is itself an iterator.
*
* @return Itself.
* | result == this
* @see java.lang.Iterable#iterator()
*/
public Iterator<T[]> iterator() {
return this;
}
/**
* Compute the factorial of n.
*/
public static BigInteger factorial(int n) {
BigInteger fact = ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply(BigInteger.valueOf(i));
}
return fact;
}
}
package de.uni_tuebingen.sfb.macke.utilities;
import java.math.BigInteger;
/**
* 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: {@link http://www.merriampark.com/comb.htm}
*
* @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
* @param <T> The type of the elements of which combinations are to be
* returned.
*/
public class Combinator<T> extends CombinatoricOperator<T> {
/**
* Initialise a new Combinator, with given elements and size of the arrays
* to be returned.
*
* @param elements
* The elements of which combinations have to be computed.
* @param r
* The size of the combinations to compute.
* @pre r should not be greater than the length of the elements, and
* not smaller than 0.
* | 0 <= r <= elements.length
* @post 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))
* @post The number of combinations left is set to the total number.
* | new.getNumLeft() == new.getTotal()
*/
public Combinator(T[] elements, int r) {
super(elements, r);
assert r <= elements.length;
}
/**
* Compute the total number of elements to return.
*
* @return 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!
* @see CombinatoricOperator#initialiseTotal(int, int)
*/
@Override
protected BigInteger initialiseTotal(int n, int r) {
BigInteger nFact = factorial(n);
BigInteger rFact = factorial(r);
BigInteger nminusrFact = factorial(n - r);
return nFact.divide(rFact.multiply(nminusrFact));
}
/**
* Compute the next array of indices.
*
* @see CombinatoricOperator#computeNext()
*/
@Override
protected void computeNext() {
int r = indices.length;
int i = r - 1;
int n = elements.length;
while (indices[i] == n - r + i) {
i--;
}
indices[i] = indices[i] + 1;
for (int j = i + 1; j < r; j++) {
indices[j] = indices[i] + j - i;
}
}
}
package de.uni_tuebingen.sfb.macke.utilities;
import java.math.BigInteger;
/**
* A class that permutes a given array of elements. It is an iterator that
* returns all permutations, successively. Thanks to Tim Tyler for the
* original implementation {@link http://mandala.co.uk/permutations/}.
*
* @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
* @param <T> The type of the array to be permuted.
*/
public class Permuter<T> extends CombinatoricOperator<T> {
/**
* Initialise a new permuter, with given array of elements to permute.
*
* @param elements
* The elements to permute.
* @post The total number is set to the factorial of the number of
* elements.
* | new.getTotal() == factorial(elements.length)
* @post The number of permutations left is set to the total number.
* | new.getNumLeft() == new.getTotal()
*/
public Permuter(T[] elements) {
super(elements, elements.length);
}
/**
* Compute the total number of elements to return.
*
* @return The factorial of the number of elements.
* | result == factorial(n)
* @see CombinatoricOperator#initialiseTotal(int, int)
*/
@Override
protected BigInteger initialiseTotal(int n, int r) {
return factorial(n);
}
/**
* Compute the next array of indices.
*
* @see CombinatoricOperator#computeNext()
*/
@Override
protected void computeNext() {
int i = indices.length - 1;
while (indices[i - 1] >= indices[i])
i = i - 1;
int j = indices.length;
while (indices[j - 1] <= indices[i - 1])
j = j - 1;
swap(i - 1, j - 1);
i++;
j = indices.length;
while (i < j) {
swap(i - 1, j - 1);
i++;
j--;
}
}
/**
* Swap the elements at positions a and b, both from the index array and
* from the element array.
*
* @param a, b
* The indices of the elements to be swapped.
* @post The elements at indices a and b of the array of indices are
* swapped.
* | new.indexes[a] = indexes[b]
* | new.indexes[b] = indexes[a]
*/
private void swap(int a, int b) {
int temp = indices[a];
indices[a] = indices[b];
indices[b] = temp;
}
}
package de.uni_tuebingen.sfb.macke.utilities;
import java.math.BigInteger;
import java.util.Arrays;
/**
* A class that sequentially returns all variations with repetition of a certain
* number out of an array of given elements.
*
* @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
* @param <T> The type of the elements of which variations are to be
* returned.
*/
public class VariatorWithRepetition<T> extends CombinatoricOperator<T> {
/**
* Initialise a new variator, with given elements and size of the arrays
* to be returned.
*
* @param elements
* The elements of which variations have to be computed.
* @param r
* The size of the variations to compute.
* @pre r should not be smaller than 0.
* | 0 <= r
* @post The total number of iterations is set to the number of elements
* to the rth power.
* | new.getTotal() == BigInteger.valueOf(elements.length).pow(r)
* @post The number of variations left is set to the total number.
* | new.getNumLeft() == new.getTotal()
*/
public VariatorWithRepetition(T[] elements, int r) {
super(elements, r);
}
/**
* Initialise the array of indices. For variations with repetition, it
* needs to be initialised with all 0s
*/
@Override
protected void initialiseIndices() {
Arrays.fill(indices, 0);
}
/**
* Compute the total number of elements to return.
*
* @see CombinatoricOperator#initialiseTotal()
*/
@Override
protected BigInteger initialiseTotal(int n, int r) {
return BigInteger.valueOf(n).pow(r);
}
/**
* Compute the next array of indices.
*
* @see CombinatoricOperator#computeNext()
*/
@Override
protected void computeNext() {
int i = indices.length - 1;
int n = elements.length;
while (++indices[i] == n && i > 0) {
indices[i--] = 0;
}
}
}
package de.uni_tuebingen.sfb.macke;
import de.uni_tuebingen.sfb.macke.utilities.*;
import java.util.Arrays;
/**
* A class for testing the combinatoric operators.
*
* @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
*/
public class PermuterTest {
/**
*
*
* @param args
*/
public static void main(String args[]) {
final Integer[] data = new Integer[3];
for (int i = 0; i < data.length; i++) {
data[i] = i;
}
for (Integer[] variation : new Permuter<Integer>(data)) {
out.println(Arrays.toString(variation));
}
out.println();
for (int i = 0; i <= data.length; i++) {
for (Integer[] combination : new Combinator<Integer>(data, i)) {
out.println(Arrays.toString(combination));
}
}
out.println();
for (int i = 0; i <= data.length; i++) {
for (Integer[] variation : new VariatorWithRepetition<Integer>(data,i)) {
out.println(Arrays.toString(variation));
}
}
}
}