Package 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:
main
Belongs to CDK module:
standard
Keywords:
permutation
Created on:
2009-09-09

  • Constructor Details

    • 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 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