Friday, March 16, 2012

Combination Generator

Posted by Unknown at 2:38 AM


Introduction

The CombinationGenerator Java class systematically generates all combinations of n elements, taken r at a time. The algorithm is described by Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 284-286.
The class is very easy to use. Suppose that you wish to generate all possible three-letter combinations of the letters "a", "b", "c", "d", "e", "f", "g". Put the letters into an array. Keep calling the combination generator's getNext () method until there are no more combinations left. The getNext () method returns an array of integers, which tell you the order in which to arrange your original array of letters. Here is a snippet of code which illustrates how to use the CombinationGenerator class.
String[] elements = {"a", "b", "c", "d", "e", "f", "g"};
int[] indices;
CombinationGenerator x = new CombinationGenerator (elements.length, 3);
StringBuffer combination;
while (x.hasMore ()) {
  combination = new StringBuffer ();
  indices = x.getNext ();
  for (int i = 0; i < indices.length; i++) {
    combination.append (elements[indices[i]]);
  }
  System.out.println (combination.toString ());
}
Another example of the usage of the CombinationGenerator is shown below in connection with the Zen Archery problem.

Source Code

The source code is free for you to use in whatever way you wish.
//--------------------------------------
// Systematically generate combinations.
//--------------------------------------

import java.math.BigInteger;

public class CombinationGenerator {

  private int[] a;
  private int n;
  private int r;
  private BigInteger numLeft;
  private BigInteger total;

  //------------
  // Constructor
  //------------

  public CombinationGenerator (int n, int r) {
    if (r > n) {
      throw new IllegalArgumentException ();
    }
    if (n < 1) {
      throw new IllegalArgumentException ();
    }
    this.n = n;
    this.r = r;
    a = new int[r];
    BigInteger nFact = getFactorial (n);
    BigInteger rFact = getFactorial (r);
    BigInteger nminusrFact = getFactorial (n - r);
    total = nFact.divide (rFact.multiply (nminusrFact));
    reset ();
  }

  //------
  // Reset
  //------

  public void reset () {
    for (int i = 0; i < a.length; i++) {
      a[i] = i;
    }
    numLeft = new BigInteger (total.toString ());
  }

  //------------------------------------------------
  // Return number of combinations not yet generated
  //------------------------------------------------

  public BigInteger getNumLeft () {
    return numLeft;
  }

  //-----------------------------
  // Are there more combinations?
  //-----------------------------

  public boolean hasMore () {
    return numLeft.compareTo (BigInteger.ZERO) == 1;
  }

  //------------------------------------
  // Return total number of combinations
  //------------------------------------

  public BigInteger getTotal () {
    return total;
  }

  //------------------
  // Compute factorial
  //------------------

  private static BigInteger getFactorial (int n) {
    BigInteger fact = BigInteger.ONE;
    for (int i = n; i > 1; i--) {
      fact = fact.multiply (new BigInteger (Integer.toString (i)));
    }
    return fact;
  }

  //--------------------------------------------------------
  // Generate next combination (algorithm from Rosen p. 286)
  //--------------------------------------------------------

  public int[] getNext () {

    if (numLeft.equals (total)) {
      numLeft = numLeft.subtract (BigInteger.ONE);
      return a;
    }

    int i = r - 1;
    while (a[i] == n - r + i) {
      i--;
    }
    a[i] = a[i] + 1;
    for (int j = i + 1; j < r; j++) {
      a[j] = a[i] + j - i;
    }

    numLeft = numLeft.subtract (BigInteger.ONE);
    return a;

  }
}

Zen Archery

In his book Wonders of Numbers (Oxford: Oxford University Press, 2001), pp. 275-276, Clifford Pickover posed a "Zen Archery" problem. In its simplest form, there is a target with 24 numbers on it. The archer must shoot 5 arrows at the target and hit numbers adding up to 200. The 24 numbers on the target are
97,101,139,41,37,31,29,89,23,19,8,13,

131,19,73,97,19,139,79,67,61,17,113,127
Pickover posed a similar problem at Archery by the Numbers. This is really a combinatorial problem -- given the 24 numbers taken 5 at a time, which unique combinations add up to 200?
There is some quick and dirty Java code on the Web, associated with Pickover's book, which solves the Zen archery problem for the 24 numbers given. However, it is not exactly a model of good programming, and it even assumes some foreknowledge of the answer in the code, i.e. the fact that all combinations adding up to 200 include the number 8.
Using our CombinationGenerator class, we can write a neater, more general solution of the Zen archery problem (ZenArchery.java) as follows:
import java.util.*;
import java.math.*;

public abstract class ZenArchery {

  private static int getSum (Vector v) {
    int sum = 0;
    Integer n;
    for (int i = 0; i < v.size (); i++) {
      n = (Integer) v.elementAt (i);
      sum += n.intValue ();
    }
    return sum;
  }

  public static Vector compute (int[] array, int atATime, int desiredTotal) {
    int[] indices;
    CombinationGenerator gen = new CombinationGenerator (array.length, atATime);
    Vector results = new Vector ();
    Vector combination;
    BigInteger numCombinations = gen.getTotal ();
    System.out.println ("Num combinations to test " + numCombinations.toString ());
    int sum;
    Integer intObj;
    while (gen.hasMore ()) {
      combination = new Vector ();
      indices = gen.getNext ();
      for (int i = 0; i < indices.length; i++) {
        intObj = new Integer (array[indices[i]]);
        combination.addElement (intObj);
      }
      sum = getSum (combination);
      if (sum == desiredTotal) {
        Collections.sort (combination);
        if (!results.contains (combination)) {
          System.out.println (combination.toString ());
          results.addElement (combination);
        }
      }
    }
    return results;
  }

  public static void main (String[] args) {
    int array[]={97,101,139,41,37,31,29,89,23,19,8,13,
                 131,19,73,97,19,139,79,67,61,17,113,127};
    Vector results = ZenArchery.compute (array, 5, 200);
    System.out.println ("Num results " + results.size ());
  }

}
Here is the output from running the ZenArchery class with Pickover's data:
Num combinations to test 42504
[8, 17, 37, 41, 97]
[8, 23, 31, 41, 97]
[8, 13, 37, 41, 101]
[8, 19, 31, 41, 101]
[8, 23, 31, 37, 101]
[8, 13, 17, 61, 101]
[8, 13, 17, 23, 139]
[8, 23, 41, 61, 67]
[8, 19, 19, 41, 113]
[8, 17, 41, 61, 73]
[8, 13, 29, 37, 113]
[8, 19, 23, 37, 113]
[8, 19, 29, 31, 113]
[8, 13, 17, 31, 131]
[8, 13, 29, 61, 89]
[8, 13, 23, 29, 127]
[8, 23, 29, 67, 73]
[8, 23, 29, 61, 79]
[8, 13, 19, 29, 131]
[8, 17, 19, 29, 127]
[8, 17, 29, 67, 79]
[8, 19, 23, 61, 89]
[8, 13, 23, 67, 89]
[8, 17, 19, 67, 89]
[8, 13, 17, 73, 89]
[8, 19, 19, 23, 131]
[8, 17, 23, 73, 79]
Num results 27