/*
* Copyright 2004-2023 H2 Group. Multiple-Licensed under the MPL 2.0,
* and the EPL 1.0 (https://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
*
* @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) {
throw DbException.getInternalError("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.
*
* @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.
*
* @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}.
*/
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.
*
* @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.
*
* @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.
*
* @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;
}
}