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

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

Type Parameters:

T - The type of the array to be permuted.

All Implemented Interfaces:

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

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

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 http://mandala.co.uk/permutations/.

Author:

Hendrik Maryns

Field Summary

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

elements, indices

Constructor Summary

Permuter(T[] elements)
Initialize a new permuter, with given array of elements to permute.

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.
private void	swap(int a, int b) Swap the elements at positions a and b, both from the index array and from the element array.

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

Permuter

public Permuter(T[] elements)

Initialize a new permuter, with given array of elements to permute.

Parameters:

elements - The elements to permute.

Postcondition:

The total number is set to the factorial of the number of elements.

| new.getTotal() ==
       factorial(elements.length)

Postcondition:

The number of permutations 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.

| result == factorial(n)

computeNext

protected void computeNext()

Compute the next array of indices.

Specified by:

computeNext in class CombinatoricOperator<T>

swap

private void swap(int a,
                  int b)

Swap the elements at positions a and b, both from the index array and from the element array.

Parameters:

a - The first index of the elements to be swapped.

b - The second index of the elements to be swapped.

Postcondition:

The elements at indices a and b of the array of indices are swapped.

| new.indexes[a] = indexes[b] |
       new.indexes[b] = indexes[a]