まずは、1つの順列のみを必要とする問題で使用するクラス（ただし、
\begin{align} 10! &= 3628800 < 3.7\times 10^6\\ 11! &= 39916800 < 4\times 10^7\\ 12! &= 479001600 > 4.7\times 10^8 \end{align}
を考慮すると、探索範囲の大きさが1つの順列のみによって定まる場合、使用可能なのはせいぜい順列の長さが11までか）です。例えば以下の問題で役に立ちます。
AtCoder Beginner Contest 319 C - False Hope
AtCoder Beginner Contest 320 C - Slot Strategy 2 (Easy)
※以下、どのクラスでもpermフィールドがprivateになっていませんが、Mainクラスからは読み出しのみ行い、競プロ向けの個人的利用のみを前提としているため良しとしています。また、探索実行のためにはbuildToSearchメソッドを呼び出します。
import java.util.stream.IntStream;
/**
* 1つの順列を用いて全探索する
*/
final class SinglePermutation {
private int[] init;
int[] perm;
private boolean[] used;
private void process() {
// 順列生成完了後に実行したい処理をここに書く
}
/**
* 順列の長さをもとにインスタンスを生成する
* @param size 順列の長さ
* @return 引数で指定した長さを持つ順列全探索用インスタンス
* @throws IllegalArgumentException （{@code size < 1} の場合）
*/
public static SinglePermutation instantiateWithSizeOf(int size) {
if (size < 1) {
throw new IllegalArgumentException();
}
return new SinglePermutation(size);
}
/**
* 必要となる順列を全て生成し、それぞれに対して所望の探索処理を実行する
*/
public void buildToSearch() {
build(0);
}
/**
* 順列の転倒数を求める。
* @return 順列の転倒数
*/
public int findInversionNumber() {
int res = 0;
for (int i = 0; i < this.perm.length; ++i) {
for (int j = i + 1; j < this.perm.length; ++j) {
if (this.perm[i] > this.perm[j]) {
res += 1;
}
}
}
return res;
}
private SinglePermutation(int size) {
this.init = IntStream.range(0, size).toArray();
this.perm = new int[size];
this.used = new boolean[size];
}
private void build(int depth) {
if (depth == this.init.length) {
process();
return;
}
for (int i = 0; i < this.init.length; ++i) {
if (this.used[i]) {
continue;
}
this.perm[depth] = this.init[i];
this.used[i] = true;
build(depth + 1);
this.used[i] = false;
}
}
}
次は、等しい長さを持つ複数の順列を探索対象とする問題で使用するクラスです。
import java.util.stream.IntStream;
/**
* 0から{@code n - 1}までの整数を各要素とする等しい長さの2つ以上の順列たちにより全探索を行う
*/
final class FixedLengthMultiPermutations {
private int numOfPerm;
private int[] init;
int[][] perm;
private boolean[][] used;
private void process() {
// 順列生成完了後に実行したい処理をここに書く
}
/**
* 必要となる順列を全て生成し、それぞれに対して所望の探索処理を実行する
*/
public void buildToSearch() {
build(0, 0);
}
/**
* 指定した順列の転倒数を求める。
* @param r 対象となる順列の番号（0-indexed）
* @return 対象とした順列の転倒数
*/
public int findInversionNumberOf(int r) {
final int[] targetPerm = this.perm[r];
int res = 0;
for (int i = 0; i < targetPerm.length; ++i) {
for (int j = i + 1; j < targetPerm.length; ++j) {
if (targetPerm[i] > targetPerm[j]) {
res += 1;
}
}
}
return res;
}
/**
* 順列の転倒数の合計を求める。
* @return 転倒数の合計
*/
public int findSumOfInversionNumber() {
int res = 0;
for (int i = 0; i < this.numOfPerm; ++i) {
res += findInversionNumberOf(i);
}
return res;
}
/**
* 順列の個数と各順列の長さから順列全探索用インスタンスを生成するビルダー<br>
* （デフォルトでは長さが3の順列を2個持つ）
*/
public static class Builder {
private int numOfPerm = 2;
private int size = 3;
/**
* 順列の個数を設定する
* @param numOfPerm 順列の個数
* @return このビルダー自身への参照
* @throws {@code numOfPerm < 2} の場合
*/
public Builder setNumOfPerm(int numOfPerm) {
if (numOfPerm < 2) {
throw new IllegalArgumentException();
}
this.numOfPerm = numOfPerm;
return this;
}
/**
* 各順列の長さを設定する
* @param size 各順列の長さ
* @return このビルダー自身への参照
* @throws {@code size < 1} の場合
*/
public Builder setSize(int size) {
if (size < 1) {
throw new IllegalArgumentException();
}
this.size = size;
return this;
}
/**
* 順列の個数と各順列の長さから順列全探索用インスタンスを生成する
* @return 順列の個数と各順列の長さから生成される順列全探索用インスタンス
*/
public FixedLengthMultiPermutations build() {
return new FixedLengthMultiPermutations(this.numOfPerm, this.size);
}
}
private FixedLengthMultiPermutations(int numOfPerm, int size) {
this.numOfPerm = numOfPerm;
this.init = IntStream.range(0, size).toArray();
this.perm = new int[numOfPerm][size];
this.used = new boolean[numOfPerm][size];
}
private void build(int permIdx, int depth) {
if (permIdx == this.numOfPerm) {
process();
return;
}
if (depth == this.init.length) {
build(permIdx + 1, 0);
return;
}
for (int i = 0, f = this.init.length; i < f; ++i) {
if (this.used[permIdx][i]) {
continue;
}
this.perm[permIdx][depth] = this.init[i];
this.used[permIdx][i] = true;
build(permIdx, depth + 1);
this.used[permIdx][i] = false;
}
}
}
最後に、それぞれが異なる長さを持ち得るような複数の順列たちを探索対象とする問題で使用するクラスです。
import java.util.stream.IntStream;
/**
* 異なる長さを持つ2つ以上の順列たちにより全探索を実行する
*/
final class VariableLengthMultiPermutations {
private int numOfPerm;
private int[][] init;
int[][] perm;
private boolean[][] used;
private void process() {
// 順列を生成した後に行いたい処理をここに書く
}
/**
* それぞれの順列の長さをもとにインスタンスを生成する
* @param sizes それぞれの順列の長さ
* @return それぞれの引数で指定した長さを持つ順列全探索用インスタンス
* @throws （{@code sizes.length < 2 || sizes[i] < 1}） の場合
*/
public static VariableLengthMultiPermutations instantiateWithSizesOf(int... sizes) {
if (sizes.length < 2) {
throw new IllegalArgumentException();
}
for (int i = 0; i < sizes.length; ++i) {
if (sizes[i] < 1) {
throw new IllegalArgumentException();
}
}
return new VariableLengthMultiPermutations(sizes);
}
/**
* 必要となる順列を全て生成し、それぞれに対して所望の探索処理を実行する
*/
public void buildToSearch() {
build(0, 0);
}
/**
* 指定した順列の転倒数を求める。
* @param r 対象となる順列の番号（0-indexed）
* @return 対象とした順列の転倒数
*/
public int findInversionNumberOf(int r) {
final int[] targetPerm = this.perm[r];
int res = 0;
for (int i = 0; i < targetPerm.length; ++i) {
for (int j = i + 1; j < targetPerm.length; ++j) {
if (targetPerm[i] > targetPerm[j]) {
res += 1;
}
}
}
return res;
}
/**
* 順列の転倒数の合計を求める。
* @return 転倒数の合計
*/
public int findSumOfInversionNumber() {
int res = 0;
for (int i = 0; i < this.numOfPerm; ++i) {
res += findInversionNumberOf(i);
}
return res;
}
private VariableLengthMultiPermutations(int... sizes) {
this.numOfPerm = sizes.length;
this.init = new int[this.numOfPerm][];
this.perm = new int[this.numOfPerm][];
this.used = new boolean[this.numOfPerm][];
for (int i = 0; i < this.numOfPerm; ++i) {
this.init[i] = IntStream.range(0, sizes[i]).toArray();
this.perm[i] = new int[sizes[i]];
this.used[i] = new boolean[sizes[i]];
}
}
private void build(int permIdx, int depth) {
if (permIdx == this.numOfPerm) {
process();
return;
}
if (depth == this.init[permIdx].length) {
build(permIdx + 1, 0);
return;
}
for (int i = 0, f = this.init[permIdx].length; i < f; ++i) {
if (this.used[permIdx][i]) {
continue;
}
this.perm[permIdx][depth] = this.init[permIdx][i];
this.used[permIdx][i] = true;
build(permIdx, depth + 1);
this.used[permIdx][i] = false;
}
}
}
