Package org.h2.util

Class Permutations<T>

java.lang.Object
org.h2.util.Permutations<T>
Type Parameters:
T - the element type

public class Permutations<T> extends 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
     
    private final T[]
     
    private final int[]
     
    private final int
     
    private final int
     
    private final T[]
     
  • Constructor Summary

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

    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
    Move the index forward a notch.
    boolean
    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
    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 Details

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

    • Permutations

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

    • 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