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 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
-
-
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.
-
-
-
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 arrayout
- 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 arrayout
- the target arraym
- 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
-
-