bcds.tools
Class CombinationGenerator

java.lang.Object
  bcds.tools.CombinationGenerator

public class CombinationGenerator
extends java.lang.Object

CombinationGenerator systematically generates all combinations of n elements, taken r at a time.

This implementation was copied from: http://www.merriampark.com/comb.htm. The javadoc comments was added by Juan Segovia.

The algorithm is described in Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 284-286.

Example of use:

    {
       CombinationGenerator cg = new CombinationGenerator(7, 4);

       while ( cg.hasMore() ) {
          int [] a = cg.getNext();

          System.out.println();
          for (int k=0; k < a.length; k++) {
              System.out.printf("%d ", a[k]);
          }
       }
       ...
 

The above will print:

  0 1 2 3
  0 1 2 4
  0 1 2 5
  0 1 2 6
  0 1 3 4
  0 1 3 5
  0 1 3 6
  0 1 4 5
  ...
  1 4 5 6
  2 3 4 5
  2 3 4 6
  2 3 5 6
  2 4 5 6
  3 4 5 6
 

As can be seen, each invocation of getnext returns a series of object selectors (indexes) that should go in each position.

Author:

K. Rosen, Juan Segovia S.

Constructor Summary

CombinationGenerator(int n, int r)
Instantiates a combination generator for n elements, taken r at a time.

Method Summary

int[]	getNext() Returns a new combination of indexes.
java.math.BigInteger	getNumLeft() Returns the number of combinations not yet consumed with getNext().
java.math.BigInteger	getTotal() Returns the total number of combinations.
boolean	hasMore() Returns true if {#link getNumLeft} > 0.
void	reset() Resets this generator, as if it were just instantiated.

Methods inherited from class java.lang.Object

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

Constructor Detail

CombinationGenerator

public CombinationGenerator(int n,
                            int r)

Instantiates a combination generator for n elements, taken r at a time.

Method Detail

reset

public void reset()

Resets this generator, as if it were just instantiated.

getNumLeft

public java.math.BigInteger getNumLeft()

Returns the number of combinations not yet consumed with getNext().

hasMore

public boolean hasMore()

Returns true if {#link getNumLeft} > 0.

getTotal

public java.math.BigInteger getTotal()

Returns the total number of combinations.

getNext

public int[] getNext()

Returns a new combination of indexes.

Throws:

ArrayIndexOutofBoundsException - if called when hasMore() == false.