Package org.openscience.cdk.graph
Class Permutor
java.lang.Object
org.openscience.cdk.graph.Permutor
- Direct Known Subclasses:
AtomContainerPermutor
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:
- main
- Belongs to CDK module:
- standard
- Keywords:
- permutation
- Created on:
- 2009-09-09
-
Constructor Summary
ConstructorsConstructorDescriptionPermutor
(int size) Create a permutor that will generate permutations of numbers up tosize
. -
Method Summary
Modifier and TypeMethodDescriptionint
Calculate the max possible rank for permutations of N numbers.int[]
Get the permutation that is currently being used.int[]
Get the next permutation in the list.int[]
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.
-
Constructor Details
-
Permutor
public Permutor(int size) Create a permutor that will generate permutations of numbers up tosize
.- Parameters:
size
- the size of the permutations to generate
-
-
Method Details
-
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
-