org.knime.base.util.math
Class Combinations

java.lang.Object
  extended by 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


Copyright, 2003 - 2010. All rights reserved.
University of Konstanz, Germany.
Chair for Bioinformatics and Information Mining, Prof. Dr. Michael R. Berthold.
You may not modify, publish, transmit, transfer or sell, reproduce, create derivative works from, distribute, perform, display, or in any way exploit any of the content, in whole or in part, except as otherwise expressly permitted in writing by the copyright owner or as specified in the license file distributed with this product.