sjm.combinatorics
Class Combinations

java.lang.Object
  |
  +--sjm.combinatorics.Combinations

public class Combinations

extends java.lang.Object

implements java.util.Enumeration

The Combinations class provides an enumeration of all subsets of a group of n objects taken r at a time. The constructor for Combinations accepts the group as an array of Objects, along with the number to select.

For example, to choose 3 boys from a list of 5, begin with an array of names:

     Object[] boys = 
         {"Alfred", "Ben", "Carl", "Drew", "Edwin"};
 

To see all combinations of these 5 names taken 3 at a time, create and use a Combinations enumeration:

     Combinations c = new Combinations(boys, 3);
     while (c.hasMoreElements()) {
         Object[] combo = (Object[])c.nextElement();
         for (int i = 0; i < combo.length; i++) {
             System.out.print((String)combo[i] + " ");
         }
     System.out.println();
     }
 

This will print out a 10 line list:

 	Alfred Ben Carl 
 	Alfred Ben Drew 
 	Alfred Ben Edwin 
 	Alfred Carl Drew 
 	Alfred Carl Edwin 
 	Alfred Drew Edwin 
 	Ben Carl Drew 
 	Ben Carl Edwin 
 	Ben Drew Edwin 
 	Carl Drew Edwin 
 

Field Summary

protected boolean	hasMore
protected java.lang.Object[]	inArray
protected int[]	index
protected int	m
protected int	n

Constructor Summary

Combinations(java.lang.Object[] inArray, int m)
Create a Combination to enumerate through all subsets of the supplied Object array, selecting 'm' at a time.

Method Summary

boolean	hasMoreElements()
protected void	moveIndex() Move the index forward a notch.
java.lang.Object	nextElement()
protected int	rightmostIndexBelowMax()

Methods inherited from class java.lang.Object

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

Field Detail

inArray

protected java.lang.Object[] inArray

n

protected int n

m

protected int m

index

protected int[] index

hasMore

protected boolean hasMore

Constructor Detail

Combinations

public Combinations(java.lang.Object[] inArray,
                    int m)
             throws CombinatoricException

Create a Combination to enumerate through all subsets of the supplied Object array, selecting 'm' at a time.

Parameters:

Object[] - inArray the group to choose from

m - int the number to select in each choice

Throws:

combinatorics.CombinatoricException - if m is greater than the length of inArray, or less than 0.

Method Detail

hasMoreElements

public boolean hasMoreElements()

Specified by:

hasMoreElements in interface java.util.Enumeration

Returns:

true, unless we have already returned the last combination.

moveIndex

protected void moveIndex()

Move the index forward a notch. The algorithm finds the rightmost index element that can be incremented, increments it, and then changes the elements to the right to each be 1 plus the element on their left.

For example, if an index of 5 things taken 3 at a time is at {0 3 4}, only the 0 can be incremented without running out of room. The next index is {1, 1+1, 1+2) or {1, 2, 3}. This will be followed by {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}.

The algorithm is from "Applied Combinatorics", by Alan Tucker.

nextElement

public java.lang.Object nextElement()

Specified by:

nextElement in interface java.util.Enumeration

Returns:

java.lang.Object, the next combination from the supplied Object array.

Actually, an array of Objects is returned. The declaration must say just "Object", since the Combinations class implements Enumeration, which declares that the "nextElement()" returns a plain Object. Users must cast the returned object to (Object[]).

rightmostIndexBelowMax

protected int rightmostIndexBelowMax()

Returns:

int, the index which can be bumped up.