/*
* Copyright 2004-2019 H2 Group. Multiple-Licensed under the MPL 2.0,
* and the EPL 1.0 (http://h2database.com/html/license.html).
* Initial Developer: H2 Group
*
* According to a mail from Alan Tucker to Chris H Miller from IBM,
* the algorithm is in the public domain:
*
* Date: 2010-07-15 15:57
* Subject: Re: Applied Combinatorics Code
*
* Chris,
* The combinatorics algorithms in my textbook are all not under patent
* or copyright. They are as much in the public domain as the solution to any
* common question in an undergraduate mathematics course, e.g., in my
* combinatorics course, the solution to the problem of how many arrangements
* there are of the letters in the word MATHEMATICS. I appreciate your due
* diligence.
* -Alan
*/
package org.h2.util;
import org.h2.message.DbException;
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
Type parameters: - <T> – the element type
/**
* 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
*
* @param <T> the element type
*/
public class Permutations<T> {
private final T[] in;
private final T[] out;
private final int n, m;
private final int[] index;
private boolean hasNext = true;
private Permutations(T[] in, T[] out, int m) {
this.n = in.length;
this.m = m;
if (n < m || m < 0) {
DbException.throwInternalError("n < m or m < 0");
}
this.in = in;
this.out = out;
index = new int[n];
for (int i = 0; i < n; i++) {
index[i] = i;
}
// The elements from m to n are always kept ascending right to left.
// This keeps the dip in the interesting region.
reverseAfter(m - 1);
}
Create a new permutations object.
Params: - in – the source array
- out – the target array
Type parameters: - <T> – the type
Returns: the generated permutations object
/**
* Create a new permutations object.
*
* @param <T> the type
* @param in the source array
* @param out the target array
* @return the generated permutations object
*/
public static <T> Permutations<T> create(T[] in, T[] out) {
return new Permutations<>(in, out, in.length);
}
Create a new permutations object.
Params: - in – the source array
- out – the target array
- m – the number of output elements to generate
Type parameters: - <T> – the type
Returns: the generated permutations object
/**
* Create a new permutations object.
*
* @param <T> the type
* @param in the source array
* @param out the target array
* @param m the number of output elements to generate
* @return the generated permutations object
*/
public static <T> Permutations<T> create(T[] in, T[] out, int m) {
return new Permutations<>(in, out, m);
}
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}.
/**
* 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}.
*/
private void moveIndex() {
// find the index of the first element that dips
int i = rightmostDip();
if (i < 0) {
hasNext = false;
return;
}
// find the least greater element to the right of the dip
int leastToRightIndex = i + 1;
for (int j = i + 2; j < n; j++) {
if (index[j] < index[leastToRightIndex] && index[j] > index[i]) {
leastToRightIndex = j;
}
}
// switch dip element with least greater element to its right
int t = index[i];
index[i] = index[leastToRightIndex];
index[leastToRightIndex] = t;
if (m - 1 > i) {
// reverse the elements to the right of the dip
reverseAfter(i);
// reverse the elements to the right of m - 1
reverseAfter(m - 1);
}
}
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
/**
* Get the index of the first element from the right that is less
* than its neighbor on the right.
*
* @return the index or -1 if non is found
*/
private int rightmostDip() {
for (int i = n - 2; i >= 0; i--) {
if (index[i] < index[i + 1]) {
return i;
}
}
return -1;
}
Reverse the elements to the right of the specified index.
Params: - i – the index
/**
* Reverse the elements to the right of the specified index.
*
* @param i the index
*/
private void reverseAfter(int i) {
int start = i + 1;
int end = n - 1;
while (start < end) {
int t = index[start];
index[start] = index[end];
index[end] = t;
start++;
end--;
}
}
Go to the next lineup, and if available, fill the target array.
Returns: if a new lineup is available
/**
* Go to the next lineup, and if available, fill the target array.
*
* @return if a new lineup is available
*/
public boolean next() {
if (!hasNext) {
return false;
}
for (int i = 0; i < m; i++) {
out[i] = in[index[i]];
}
moveIndex();
return true;
}
}