net.sf.colossus.util

Class PermGen

java.lang.Object

net.sf.colossus.util.PermGen

 class PermGen
extends java.lang.Object

This class is a permutation generator. The permutations are generated using Dershowitz's method, meaning that a permutation only differs by the previous permutation by a single interchange of two adjacent elements. In many problem domains this allows a efficient dynamic update of a permutation function.

Author:

Peter Unold

See Also:

"Dershowitz, Nachum. "A simplified loop - free algorithm for generating permutations" BIT - 15 1975 158 - 164", Dershowitz's Permutation Generator

Field Summary

Fields

Modifier and Type	Field and Description
(package private) int[]	m_d
(package private) int[]	m_l
(package private) int[]	m_p
(package private) int	m_size
(package private) int[]	m_t

Constructor Summary

Constructors

Constructor and Description
PermGen(int size)

Method Summary

Methods

Modifier and Type	Method and Description
int[]	getCurrent() get the current permutation
int	getNext() generates the next permutation.
static void	main(java.lang.String[] args) Unit test for PermGen.

Methods inherited from class java.lang.Object

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

Field Detail

m_p

int[] m_p

m_l

int[] m_l

m_t

int[] m_t

m_d

int[] m_d

m_size

int m_size

Constructor Detail

PermGen

PermGen(int size)

Method Detail

getNext

public int getNext()

generates the next permutation. If the function returns n, then the elements at position n and n + 1 in the previous permutation were interchanged to get the new permutation.

Returns:

the index of the lower element which was interchanged or - 1 if the last permutation has been reached.

getCurrent

public int[] getCurrent()

get the current permutation

main

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

Unit test for PermGen.