net.paulhertz.util
Class Permutator

java.lang.Object
  net.paulhertz.util.Permutator

public class Permutator
extends Object

Maintains an ArrayList of Integer initialized in ascending order, and steps it to each successive permutation. The next permutation is the one that would appear next in a sorted list of all permutations, where the sorting function orders in ascending order. In the final permutation, each number is greater than the previous and no more permutations are possible.

This class is particularly intended for permutation of the indices of arrays of objects.

TODO permutations of m objects taken n at a time.

Constructor Summary

Permutator(int size)

Method Summary

ArrayList<Integer>	getPerm() Returns the permutation array.
ArrayList<Integer>	getPermCopy() Returns a copy of the permutation array: call this if you feel the urge to modify the array.
int	getSize()
void	initPerm() Initializes the permutation array to integer values from 0 to size - 1.
static String	listToString(ArrayList<Integer> permArray) Converts elements in the supplied permutation to a string.
static String	listToString(int[] permArray) Converts elements in the supplied permutation to a string.
boolean	nextPerm() Steps to next permutation of the permutation array, returns false if the last permutation has been reached.
static boolean	nextPerm(ArrayList<Integer> permArray) Steps to next permutation of an ArrayList of Integer, returns false if the last permutation has been reached.
static boolean	nextPerm(int[] permArray) Steps to next permutation of an array of integers, returns false if the last permutation has been reached.
void	setPerm(ArrayList<Integer> perm) Set the permutation array to the supplied ArrayList of Integer.
String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

Permutator

public Permutator(int size)

Method Detail

initPerm

public void initPerm()

Initializes the permutation array to integer values from 0 to size - 1.

getPerm

public ArrayList<Integer> getPerm()

Returns the permutation array. Any modifications to the size of the array can cause tragic errors in later calls to this class. If you want to mess with the permutation array, call getPermCopy.

Returns:

the perm

setPerm

public void setPerm(ArrayList<Integer> perm)

Set the permutation array to the supplied ArrayList of Integer.

Parameters:

perm - an ArrayList of Integer to set

getPermCopy

public ArrayList<Integer> getPermCopy()

Returns a copy of the permutation array: call this if you feel the urge to modify the array.

Returns:

an ArrayList of Integer, copy of the permutation array

getSize

public int getSize()

Returns:

the size of the permutation array

nextPerm

public boolean nextPerm()

Steps to next permutation of the permutation array, returns false if the last permutation has been reached. The next permutation is the one that would appear next in a sorted list of all permutations, where the sorting function orders in ascending order. In the final permutation, each number is greater than the previous and no more permutations are possible. This is an implementation of an algorithm described by Edsger Dijkstra in "A Discipline of Programming" [Prentice-Hall, 1976].

Returns:

true if the permutation was successfully generated, otherwise false

toString

public String toString()

Overrides:

toString in class Object

nextPerm

public static boolean nextPerm(ArrayList<Integer> permArray)

Steps to next permutation of an ArrayList of Integer, returns false if the last permutation has been reached. The next permutation is the one that would appear next in a sorted list of all permutations, where the sorting function orders in ascending order. In the final permutation, each number is greater than the previous and no more permutations are possible. This is an implementation of an algorithm described by Edsger Dijkstra in "A Discipline of Programming" [Prentice-Hall, 1976].

Returns:

true if the permutation was successfully generated, otherwise false

nextPerm

public static boolean nextPerm(int[] permArray)

Steps to next permutation of an array of integers, returns false if the last permutation has been reached. The next permutation is the one that would appear next in a sorted list of all permutations, where the sorting function orders in ascending order. In the final permutation, each number is greater than the previous and no more permutations are possible. This is an implementation of an algorithm described by Edsger Dijkstra in "A Discipline of Programming" [Prentice-Hall, 1976].

Returns:

true if the permutation was successfully generated, otherwise false

listToString

public static String listToString(ArrayList<Integer> permArray)

Converts elements in the supplied permutation to a string.

Parameters:

permArray - an ArrayList of Integer

Returns:

a String representing the values in the permutation

listToString

public static String listToString(int[] permArray)

Converts elements in the supplied permutation to a string.

Parameters:

permArray - an ArrayList of Integer

Returns:

a String representing the values in the permutation