net.sf.colossus.util
Class PermGen

java.lang.Object
  extended by 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
(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
PermGen(int size)
           
 
Method Summary
 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.