Package org.openscience.cdk.graph

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