org.uacalc.util
Class PermutationGenerator

java.lang.Object
  org.uacalc.util.PermutationGenerator

public class PermutationGenerator
extends java.lang.Object

This class is used to help generate permutations of arrays. It has has one public method: nextIndex() which returns the index i such that the next permutation should interchange the i^th and following elements.

Using this one can start with a fixed array or List and modify it in place, generating all permutations of the elements. Note if the two elements to be interchanged are the same, nextIndex() can just be called again.

This class has static methods giving both an Iterator and an (in place) ArrayIncrementor.

This uses the Johnson-Trotter algorithm: start with the indentity permutation and with the direction of each integer left. If there is a mobile integer k, find the largest one, swap it with the neighbor it points to, and reverse the arrows of all integers larger than k. Mobile means pointing to a smaller integer.

Constructor Summary

PermutationGenerator(int n)

Method Summary

static ArrayIncrementor	arrayIncrementor(int[] arr) This increments arr, applying the next transposition that results in a different array.
static java.util.Iterator	iterator(int n) This iterator iterates all permutations on the set 0, ..., n-1.
static ArrayIncrementor	listIncrementor(java.util.List lst) This increments arr, applying the next transposition that results in a different array.
static void	main(java.lang.String[] args)
int	nextIndex()
void	reset()

Methods inherited from class java.lang.Object

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

Constructor Detail

PermutationGenerator

public PermutationGenerator(int n)

Method Detail

reset

public void reset()

nextIndex

public int nextIndex()

iterator

public static java.util.Iterator iterator(int n)

This iterator iterates all permutations on the set 0, ..., n-1. The iteration is on a fixed array so one needs to be careful to copy any permutation that needs to be saved.

arrayIncrementor

public static ArrayIncrementor arrayIncrementor(int[] arr)

This increments arr, applying the next transposition that results in a different array. The iteration is on a fixed array so one needs to be careful to copy any result that needs to be saved.

listIncrementor

public static ArrayIncrementor listIncrementor(java.util.List lst)

This increments arr, applying the next transposition that results in a different array. The iteration is on a fixed array so one needs to be careful to copy any result that needs to be saved.

main

public static void main(java.lang.String[] args)