Package org.h2.util

Class Permutations<T>

  • Type Parameters:
    T - the element type

    public class Permutations<T>
    extends java.lang.Object
    A class to iterate over all permutations of an array. The algorithm is from Applied Combinatorics, by Alan Tucker as implemented in http://www.koders.com/java/fidD3445CD11B1DC687F6B8911075E7F01E23171553.aspx
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private boolean hasNext  
      private T[] in  
      private int[] index  
      private int m  
      private int n  
      private T[] out  
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private Permutations​(T[] in, T[] out, int m)  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      static <T> Permutations<T> create​(T[] in, T[] out)
      Create a new permutations object.
      static <T> Permutations<T> create​(T[] in, T[] out, int m)
      Create a new permutations object.
      private void moveIndex()
      Move the index forward a notch.
      boolean next()
      Go to the next lineup, and if available, fill the target array.
      private void reverseAfter​(int i)
      Reverse the elements to the right of the specified index.
      private int rightmostDip()
      Get the index of the first element from the right that is less than its neighbor on the right.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • in

        private final T[] in
      • out

        private final T[] out
      • n

        private final int n
      • m

        private final int m
      • index

        private final int[] index
      • hasNext

        private boolean hasNext
    • Constructor Detail

      • Permutations

        private Permutations​(T[] in,
                             T[] out,
                             int m)
    • Method Detail

      • create

        public static <T> Permutations<T> create​(T[] in,
                                                 T[] out)
        Create a new permutations object.
        Type Parameters:
        T - the type
        Parameters:
        in - the source array
        out - the target array
        Returns:
        the generated permutations object
      • create

        public static <T> Permutations<T> create​(T[] in,
                                                 T[] out,
                                                 int m)
        Create a new permutations object.
        Type Parameters:
        T - the type
        Parameters:
        in - the source array
        out - the target array
        m - the number of output elements to generate
        Returns:
        the generated permutations object
      • moveIndex

        private void moveIndex()
        Move the index forward a notch. The algorithm first finds the rightmost index that is less than its neighbor to the right. This is the dip point. The algorithm next finds the least element to the right of the dip that is greater than the dip. That element is switched with the dip. Finally, the list of elements to the right of the dip is reversed. For example, in a permutation of 5 items, the index may be {1, 2, 4, 3, 0}. The dip is 2 the rightmost element less than its neighbor on its right. The least element to the right of 2 that is greater than 2 is 3. These elements are swapped, yielding {1, 3, 4, 2, 0}, and the list right of the dip point is reversed, yielding {1, 3, 0, 2, 4}.
      • rightmostDip

        private int rightmostDip()
        Get the index of the first element from the right that is less than its neighbor on the right.
        Returns:
        the index or -1 if non is found
      • reverseAfter

        private void reverseAfter​(int i)
        Reverse the elements to the right of the specified index.
        Parameters:
        i - the index
      • next

        public boolean next()
        Go to the next lineup, and if available, fill the target array.
        Returns:
        if a new lineup is available