nextPermutation

リポジトリ
next_permutation - C++ Reference
Javaにnext_permutationが無いので、作ってみた。
C++のstd::next_permutationもそうだが、順列を全列挙したいならはじめに昇順ソートしておいて、do-whileのwhileの中でnextPermutationを使わないといけない。
swapIndexは降順にならんでいる[i, toIndex)からa[i-1]をキーとしてlowerBound-1(lowerBoundには降順用来んパレータを渡す必要がある)で求まるが、C++のstd::next_permutationの中身を見てみると、ループで書いていた。
全列挙が目的ならO(!n)だし、reverseがO(n)だからオーダーは変わらないし、頻繁に呼び出すならオーバヘッドが多いからそうなっているのだろう。

public static <T> boolean nextPermutation(T[] a, int fromIndex, int toIndex, final Comparator<? super T> c){
	for (int i = toIndex - 1; i > fromIndex; --i) {
		if (c.compare(a[i-1], a[i]) < 0) { //[i,toIndex) is arranged in descending order.
			int swapIndex = toIndex;
			while (c.compare(a[i-1], a[--swapIndex]) >= 0);
			//int swapIndex = lowerBound(a, i, toIndex, a[i - 1], new Comparator<T>(){ @Override public int compare(T o1, T o2) { return -(c.compare(o1, o2)); }}) - 1;
			swap(a, i-1, swapIndex);
			reverse(a, i, toIndex);
			return true;
		}
	}
	reverse(a, fromIndex, toIndex); //turn back
	return false;
}
public static <T> boolean nextPermutation(T[] a, Comparator<? super T> c){
	return nextPermutation(a, 0, a.length, c);
}
public static <T extends Comparable <? super T>> boolean nextPermutation(T[] a, int fromIndex, int toIndex){
	return nextPermutation(a, fromIndex, toIndex, new Comparator<T>(){
		@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
	});
}
public static <T extends Comparable <? super T>> boolean nextPermutation(T[] a){
	return nextPermutation(a, 0, a.length, new Comparator<T>(){
		@Override public int compare(T o1, T o2) { return o1.compareTo(o2); }
	});
}