orbital.algorithm
Class Combinatorical

java.lang.Object
  orbital.algorithm.Combinatorical

All Implemented Interfaces:

java.io.Serializable

public abstract class Combinatorical
extends java.lang.Object
implements java.io.Serializable

Class for combinatorical operations.

This class can be used to perform combinatorical operations using the iterator methods of an instance of Combinatorical (usually) obtained via getInstance(int,boolean,int,boolean). Instances of this class will help to iterate over all elements of such a combinatorial set like permutations or combinations. Apart from methods for forward and backward navigation, a priori counting queries are provided to determine the number of elements in advance.

For example, the following code gets all 5 out of 5 permutations without repetition (i.e., the symmetric group S₅): Combinatorical c = Combinatorical.getPermutations(5, false); System.out.println(c.count()); while (c.hasNext()) { int[] v = c.next(); System.out.println(orbital.math.MathUtilities.format(v)); }

Author:

André Platzer

See Also:

getInstance(int,boolean,int,boolean), Serialized Form

Constructor Summary

Combinatorical()

Method Summary

static java.util.ListIterator	asIterator(Combinatorical c) Get an iterator view of a combinatorical iterator.
abstract int	count() Returns the number of combinatorical tuples that araise from this sequence.
static Combinatorical	getCombinations(int r, int n, boolean repetition) Get all r-combinations of n elements.
static Combinatorical	getInstance(int r, boolean combinations, int n, boolean repetition) Get a combinatorical instance.
static Combinatorical	getPermutations(int[] n) Get all (generalized) permutations elements.
static Combinatorical	getPermutations(int n, boolean repetition)
static Combinatorical	getPermutations(int r, int n, boolean repetition) Get all r-permutations of n elements.
abstract boolean	hasNext() Whether this sequence has a next combinatorical tuple.
abstract boolean	hasPrevious() Whether this sequence has a previous combinatorical tuple.
abstract int[]	next() Get the next combinatorical tuple.
abstract int[]	previous() Get the previous combinatorical tuple.

Methods inherited from class java.lang.Object

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

Constructor Detail

Combinatorical

public Combinatorical()

Method Detail

count

public abstract int count()

Returns the number of combinatorical tuples that araise from this sequence.

hasNext

public abstract boolean hasNext()

Whether this sequence has a next combinatorical tuple.

next

public abstract int[] next()

Get the next combinatorical tuple.

Returns:

the next combinatorical tuple. Note: the array returned should not be modified.

Throws:

java.util.NoSuchElementException - if not hasNext().

hasPrevious

public abstract boolean hasPrevious()

Whether this sequence has a previous combinatorical tuple.

previous

public abstract int[] previous()

Get the previous combinatorical tuple.

Returns:

the previous combinatorical tuple. Note: the array returned should not be modified.

Throws:

java.util.NoSuchElementException - if not hasPrevious().

getInstance

public static Combinatorical getInstance(int r,
                                         boolean combinations,
                                         int n,
                                         boolean repetition)

Get a combinatorical instance.

Parameters:

r - the size of the tuples. The number of elements to choose out of n.

combinations - whether only combinations are allowed, or every permutation. Permutations are the bijective maps from {1,...,M} to {1,...,M}. Combinations are those permutations ignoring order and(!) whose elements are always sorted. So this is like the difference between a set and a list

n - the number of elements choosable. n = |M|.

repetition - whether elements in a tuple are allowed to repeat.

See Also:

getPermutations(int, int, boolean), getCombinations(int, int, boolean)

getPermutations

public static Combinatorical getPermutations(int r,
                                             int n,
                                             boolean repetition)

Get all r-permutations of n elements.

Parameters:

r - the size of the tuples to permute. The number of elements to choose out of n per tuple.

n - the number of elements choosable. n = |M|.

repetition - whether elements in a tuple are allowed to repeat. The permutations with repetition contain n^r, those without repetition contain nPr tuples.

getPermutations

public static Combinatorical getPermutations(int n,
                                             boolean repetition)

getPermutations

public static Combinatorical getPermutations(int[] n)

Get all (generalized) permutations elements.

Parameters:

n - the numbers of elements choosable. r := n.length is the size of the tuples and n[i] is the number of elements choosable for the element at index i of the tuple. They are numbered 0, ..., n[i]-1.

getCombinations

public static Combinatorical getCombinations(int r,
                                             int n,
                                             boolean repetition)

Get all r-combinations of n elements. Combinations are those permutations ignoring order and(!) whose elements are always sorted. So this is like the difference between a set and a list.

Parameters:

r - the size of the tuples to combinate. The number of elements to choose out of n per tuple.

n - the number of elements choosable. n = |M|.

repetition - whether elements in a tuple are allowed to repeat. The combinations with repetition contain (^{n + r}_r ^-1), those without repetition contain nCr = (ⁿ_r) tuples.

asIterator

public static final java.util.ListIterator asIterator(Combinatorical c)

Get an iterator view of a combinatorical iterator.