org.openscience.cdk.graph

Class Permutor

java.lang.Object

org.openscience.cdk.graph.Permutor

Direct Known Subclasses:

AtomContainerPermutor

public class Permutor
extends Object

General permutation generator, that uses orderly generation by ranking and unranking. The basic idea is that all permutations of length N can be ordered (lexicographically) like:

 0 [0, 1, 2]
 1 [0, 2, 1]
 2 [1, 0, 2]
 ...
 

where the number to the left of each permutation is the rank - really just the index in this ordered list. The list is created on demand, by a process called unranking where the rank is converted to the permutation that appears at that point in the list.

The algorithms used are from the book "Combinatorial Generation : Algorithms, Generation, and Search" (or C.A.G.E.S.) by D.L. Kreher and D.R. Stinson. CRC Press (18 Dec 1998). ISBN-13 : 978-0849339882.

Author:

maclean

Source code:

master

Belongs to CDK module:

standard

Keywords:

permutation

Created on:

2009-09-09

Constructor Summary

Constructors

Constructor and Description
Permutor(int size) Create a permutor that will generate permutations of numbers up to size.

Method Summary

Modifier and Type	Method and Description
int	calculateMaxRank() Calculate the max possible rank for permutations of N numbers.
int[]	getCurrentPermutation() Get the permutation that is currently being used.
int[]	getNextPermutation() Get the next permutation in the list.
int[]	getRandomNextPermutation() Randomly skip ahead in the list of permutations.
int	getRank() Get the current rank.
boolean	hasNext()
void	setPermutation(int[] permutation) Set the currently used permutation.
void	setRank(int rank) Set the permutation to use, given its rank.

Methods inherited from class java.lang.Object

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

Constructor Detail

Permutor

public Permutor(int size)

Create a permutor that will generate permutations of numbers up to size.

Parameters:

size - the size of the permutations to generate

Method Detail

hasNext

public boolean hasNext()

setRank

public void setRank(int rank)

Set the permutation to use, given its rank.

Parameters:

rank - the order of the permutation in the list

setPermutation

public void setPermutation(int[] permutation)

Set the currently used permutation.

Parameters:

permutation - the permutation to use, as an int array

getRank

public int getRank()

Get the current rank.

Returns:

the current rank

getRandomNextPermutation

public int[] getRandomNextPermutation()

Randomly skip ahead in the list of permutations.

Returns:

a permutation in the range (current, N!)

getNextPermutation

public int[] getNextPermutation()

Get the next permutation in the list.

Returns:

the next permutation

getCurrentPermutation

public int[] getCurrentPermutation()

Get the permutation that is currently being used.

Returns:

the permutation as an int array

calculateMaxRank

public int calculateMaxRank()

Calculate the max possible rank for permutations of N numbers.

Returns:

the maximum number of permutations