sjm.combinatorics
Class Permutations

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

public class Permutations

extends java.lang.Object

implements java.util.Enumeration

The Permutations class provides an enumeration of all permutations of an array of objects. Each 'permutation' is an ordered list of the group.

For example, to see all of the ways we can select a school representative and an alternate from a list of 4 children, begin with an array of names::

     Object[] children = {
         "Leonardo", "Monica", "Nathan", "Olivia"};
 

To see all 2-permutations of these 4 names, create and use a Permutations enumeration:

     Permutations c = new Permutations(children, 2);
     while (c.hasMoreElements()) {
         Object[] perm = (Object[])c.nextElement();
         for (int i = 0; i < perm.length; i++) {
             System.out.print(perm[i] + " ");
         }
     System.out.println();
     }
 

This will print out:

 	Leonardo Monica 
 	Leonardo Nathan 
 	Leonardo Olivia 
 	Monica Leonardo 
 	Monica Nathan 
 	Monica Olivia 
 	Nathan Leonardo 
 	Nathan Monica 
 	Nathan Olivia 
 	Olivia Leonardo 
 	Olivia Monica 
 	Olivia Nathan 
 

Field Summary

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

Constructor Summary

Permutations(java.lang.Object[] inArray)
Create a Permutation to enumerate through all possible lineups of the supplied array of Objects.

Permutations(java.lang.Object[] inArray, int m)
Create a Permutation to enumerate through all possible lineups of the supplied array of Objects.

Method Summary

boolean	hasMoreElements()
protected void	moveIndex() Move the index forward a notch.
java.lang.Object	nextElement()
protected void	reverseAfter(int i) Reverse the index elements to the right of the specified index.
protected int	rightmostDip()

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

Permutations

public Permutations(java.lang.Object[] inArray)
             throws CombinatoricException

Create a Permutation to enumerate through all possible lineups of the supplied array of Objects.

Parameters:

Object[] - inArray the group to line up

Throws:

CombinatoricException - Should never happen with this interface

Permutations

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

Create a Permutation to enumerate through all possible lineups of the supplied array of Objects.

Parameters:

Object[] - inArray the group to line up

inArray - java.lang.Object[], the group to line up

m - int, the number of objects to use

Throws:

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 permutation.

moveIndex

protected void moveIndex()

Move the index forward a notch. The algorithm first finds the rightmost index that is less than its neighbor to the right. This is the 'dip' point. The algorithm next finds the least element to the right of the dip that is greater than the dip. That element is switched with the dip. Finally, the list of elements to the right of the dip is reversed.

For example, in a permuation of 5 items, the index may be {1, 2, 4, 3, 0}. The 'dip' is 2 -- the rightmost element less than its neighbor on its right. The least element to the right of 2 that is greater than 2 is 3. These elements are swapped, yielding {1, 3, 4, 2, 0}, and the list right of the dip point is reversed, yielding {1, 3, 0, 2, 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:

Object, the next permutation of the original Object array.

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

reverseAfter

protected void reverseAfter(int i)

Reverse the index elements to the right of the specified index.

rightmostDip

protected int rightmostDip()

Returns:

int the index of the first element from the right that is less than its neighbor on the right.