org.knime.base.util.math
Class Combinations

java.lang.Object
  org.knime.base.util.math.Combinations

public final class Combinations
extends Object

This class comes in handy if you want to compute combinations and process them in some way. A combination is a subset of k elements from a set of m elements. The rank(int[]) and unrank(long) methods are based on Gary D. Knott: "A Numbering System for Combinations", CACM, 17(1), 1974, pp. 45-46. The enumerate(Callback), and enumerate(long, long, Callback) methods are based on Charles J. Mifsud: "Algorithm 154: Combination in lexicographical order", CACM, 6(3), 1963, p. 103.

Author:

Thorsten Meinl, University of Konstanz

Nested Class Summary

static interface

Combinations.Callback Callback interface used by the various visit methods.

Constructor Summary

Combinations(int n, int k)
Create a combination object.

Method Summary

void	enumerate(Combinations.Callback callback) Enumerates all combinations and calls the callback for each combination.
void	enumerate(int threads, Combinations.Callback callback) Enumerates all combinations and calls the callback for each combination.
void	enumerate(long from, long to, Combinations.Callback callback) Enumerates all combinations from rank from until rank to (inclusive).
long	getNumberOfCombinations() Returns the number of possible combinations for n and k specified in the constructor.
static long	getNumberOfCombinations(int n, int k) Returns the number of possible combinations when selecting k elements from a set of n elements (without repetition).
static BigInteger	getNumberOfCombinationsBig(int n, int k) Returns the number of possible combinations when selecting k elements from a set of n elements (without repetition).
long	rank(int[] p) Computes the unique rank of the given combination.
int[]	unrank(long k) Creates the unique combination associated with the given rank number.

Methods inherited from class java.lang.Object

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

Constructor Detail

Combinations

public Combinations(int n,
                    int k)

Create a combination object.

Parameters:

n - the total number of elements

k - the number of selected elements

Method Detail

getNumberOfCombinations

public long getNumberOfCombinations()

Returns the number of possible combinations for n and k specified in the constructor.

Returns:

the number of combinations

rank

public long rank(int[] p)

Computes the unique rank of the given combination. The elements inside the array must be sorted ascending.

Parameters:

p - a valid combination

Returns:

the unique rank, a number between 0 and getNumberOfCombinations() - 1.

unrank

public int[] unrank(long k)

Creates the unique combination associated with the given rank number.

Parameters:

k - the rank, a number between 0 and getNumberOfCombinations() - 1.

Returns:

a valid combination

getNumberOfCombinations

public static long getNumberOfCombinations(int n,
                                           int k)

Returns the number of possible combinations when selecting k elements from a set of n elements (without repetition).

Parameters:

n - the size of the set

k - the number of selected elements

Returns:

the number of possible combinations

Throws:

ArithmeticException - if an overflow occurs during computing. In this case you can use getNumberOfCombinationsBig(int, int) instead (which is slower, but works for arbitrary big numbers).

getNumberOfCombinationsBig

public static BigInteger getNumberOfCombinationsBig(int n,
                                                    int k)

Returns the number of possible combinations when selecting k elements from a set of n elements (without repetition).

Parameters:

n - the size of the set

k - the number of selected elements

Returns:

the number of possible combinations

enumerate

public void enumerate(Combinations.Callback callback)

Enumerates all combinations and calls the callback for each combination.

Parameters:

callback - the callback class

enumerate

public void enumerate(long from,
                      long to,
                      Combinations.Callback callback)

Enumerates all combinations from rank from until rank to (inclusive). The callback is called for each combination.

Parameters:

from - the first combination to be enumerated

to - the last combination to be enumerated

callback - the callback

enumerate

public void enumerate(int threads,
                      Combinations.Callback callback)
               throws InterruptedException

Enumerates all combinations and calls the callback for each combination. The enumeration process is carried out in parallel by several threads.

Parameters:

threads - the number of threads to use

callback - the callback class

Throws:

InterruptedException - if this thread was interrupted while waiting for the enumeration to finish