Algorithm Alley
by Shawn Bayern

Example 1:

void getBitCombinations(BitSet bs, int start, int current, int target)
{
    if (current == target) {
    // success, so store a copy of the BitSet in a Vector
    v.add(bs.clone());
    return;
    }
    if (start == a.length)
        return;                 // failure
    bs.set(start);
    current++;
    getBitCombinations(bs, start + 1, current, target);
    bs.clear(start);
    current--;
    getBitCombinations(bs, start + 1, current, target);
}


Example 2:  

void getBitCombinations(BitSet bs, int start, int current, int target)
{
    if (current == target) {
    // success, so process the combination in-line
    // (clone 'bs' so that we're sure it's not modified)
    foo.combinationHandlerMethod((BitSet) bs.clone());
    return;
   }
    if (start == a.length)
        return;                 // failure
    bs.set(start);
    current++;
    getBitCombinations(bs, start + 1, current, target);
    bs.clear(start);
    current--;
    getBitCombinations(bs, start + 1, current, target);
}

Example 3: 
(a)
void getBitCombinations(CombinationHandler ch,
    BitSet bs, int start, int current, int target)
{
    if (current == target) {
    // success, so process the combination in-line
    // (clone 'bs' so that we're sure it's not modified)
    ch.process((BitSet) bs.clone());
    return;
    }
    if (start == a.length)
        return;                 // failure
    bs.set(start);
    current++;
    getBitCombinations(ch, bs, start + 1, current, target);
    bs.clear(start);
    current--;
    getBitCombinations(ch, bs, start + 1, current, target);
}

(b)  
/** An interface that defines a callback method for handling combinations. */
public interface CombinationHandler {
    /** The combination-handling method, called back by the general routine. */
    public void process(BitSet combination);
}

Listing One
package com.shawnbayern.util;
import java.util.*;
import java.lang.reflect.*;

/**
 *  A class that acts as an Iterator that walks through combinations
 *  over the class's input (an array).  The order of items in each
 *  combination is, incidentally, guaranteed to be the same as the
 *  order of those same items in the original array.
 */

public class Combinations implements Iterator {

    /**
     *  For testing.
     *  Example:  java com.shawnbayern.util.Combinations abcdefg 5
     */
    public static void main(String args[]) {
        // convert the first argument into a Character[]
        char[] full = args[0].toCharArray();
        Character[] fullCollection = new Character[full.length];
        for (int i = 0; i < full.length; i++)
            fullCollection[i] = new Character(full[i]);

        // get the combination size requested
        int combSize = Integer.parseInt(args[1]);

        // print out a list of combinations
        Iterator i = new Combinations(fullCollection, combSize);
        while (i.hasNext()) {
            Character[] curComb = (Character []) i.next();
            for (int j = 0; j < curComb.length; j++)
                System.out.print(curComb[j]);
            System.out.println();
        }
    }

    Object[] a;                         // the array we handle
    int n;                              // size of combinations
    BitSet latest = null;               // shared between threads
    boolean needNewLatest = false;      // do we need a new BitSet?
    Object latestSync = new Object();   // used just for its monitor
    boolean hasNextShouldFetch = true;  // should hasNext fetch?  has
                                        // the last one been used?

    /**
     *  Returns a new Combinations Iterator for all combinations of
     *  size n out of array a.
     */
    public Combinations(Object[] a, final int n) {
        if (n > a.length)
            throw new IllegalArgumentException(
                "combination size cannot be larger than array size");
        if (n < 0)
            throw new IllegalArgumentException(
                "combination size cannot be negative");

        this.a = a;
        this.n = n;

        // start our worker thread
        Thread t = new Thread(new Runnable() {
            public void run() {
                startBitCombinationsIteration(n);
            }
        });
        t.setDaemon(true);
        t.start();
    }

    /** Returns true if we have another combination to present. */
    public boolean hasNext() {
        /*
         * This method does the actual work; next() is just a thin
         * shell that calls us (to confirm the presence of a new entry
         * and, then, to read it).
         *
         * We therefore don't want to run multiple times in a row,
         * without an intervening call to next().
         *
         * Thus, simply return status -- that is, don't do the
         * internal work involved in getting a new BitSet -- if we
         * were called more recently than next() or otherwise
         * instructed not to run.
         */
        if (!hasNextShouldFetch)
            return (latest != null);

        /*
         * After this iteration, don't run again until someone
         * else asks for us
         */
        hasNextShouldFetch = false;

        // consume the combination
        try {
            synchronized (latestSync) {
                needNewLatest = true;
                latestSync.notify();  // signal that we're ready
                latestSync.wait();    // wait for the worker thread
            }
            return (latest != null);
        } catch (InterruptedException ex) {
            // shouldn't happen
            throw new IllegalStateException(
                "hasNext shouldn't have been interrupted");
        }
    }

    /** Returns the next combination we have to present. */
    public Object next() {
        // let hasNext() do the work
        if (!hasNext())
            throw new NoSuchElementException();

        /*
         * Apply the BitSet to array a.  That is, produce a new
         * array of the same type as a and fill it with every
         * element whose index corresponds to a 1 bit in the BitSet.
         * We don't do any of the real work in determining the
         * combinations; we just use the 'latest' one that's been
         * found and let hasNext() keep it up to date.
         */
        Object c = Array.newInstance(a[0].getClass(), n);
        for (int j = 0, k = 0; j < a.length; j++)
            if (latest.get(j))
                Array.set(c, k++, a[j]);

        hasNextShouldFetch = true;        // we'll want another one
        return c;
    }

    /** Just to fulfill the contract. */
    public void remove() {
        throw new UnsupportedOperationException();
    }

    /** Starts computation of combinations. */
    private void startBitCombinationsIteration(int n) {
        BitSet bs = new BitSet();
        getBitCombinations(bs, 0, 0, n);

        /*
         * Now that our recursion's done, we need to wait until a new
         * 'latest' is needed and then set it to null to indicate that
         * we have nothing more to present
         */
        try {
            synchronized(latestSync) {
                while (!needNewLatest) {
                    latestSync.wait();
                }
                latest = null;
                needNewLatest = false;
                hasNextShouldFetch = false;  // nothing more to get
                latestSync.notify();         // signal that we're done
            }
        } catch (InterruptedException ex) {
            // shouldn't happen
            throw new IllegalStateException(
                "startBitCombinationsIteration "
                + "shouldn't have been interrupted");
        }
    }

    /** Recursively performs the work of startBitCombinations above. */
    private void getBitCombinations(
                BitSet bs, int start, int current, int target) {
        try {
            if (current == target) {
                synchronized(latestSync) {
                    while (!needNewLatest) {
                        latestSync.wait();  // wait until we're needed
                    }

                    /*
                     * clone it so that we can continue working on
                     * the original, preparing the next 'latest' for
                     * when it's needed
                     */
                    latest = (BitSet) bs.clone();
                    needNewLatest = false;

                    latestSync.notify();  // signal that we're done
                }
                return;
            }
        } catch (InterruptedException ex) {
            // shouldn't happen
            throw new IllegalStateException(
                "getBitCombinations shouldn't have been interrupted");
        }

        if (start == a.length)
            return;

        bs.set(start);
        current++;
        getBitCombinations(bs, start + 1, current, target);

        bs.clear(start);
        current--;
        getBitCombinations(bs, start + 1, current, target);

    }
}






