全順列を調べる問題を解くのに、C++ だと next_permutation() があリます。Java で解こうとすると、Java には next_permutation() は準備されていないので自前で実装する必要があります。
全順列の列挙（C++の場合）
1〜N までの N 個の数の全順列を試す場合、c++ では、
vector<int> ar(n);
for (int i = 0; i < n; i++) ar[i] = i;
do {
for (int i = 0; i < n; i++) {
cout << ar[i];
if (i < n - 1) cout << " ";
else cout << endl;
}
} while (next_permutation(ar.begin(), ar.end()));
のようになります。
実装方針
0 から N-1 までの N 個の数が入っている配列 ar に対して、大きさが一つ大きな配列に変換する関数を作リます。
（ここで、配列の大きさ＝配列の要素（数）を要素順に並べてできる数の大きさ、です。）
この関数は、引数の配列に対して次の配列（＝大きさがより大きな配列）が存在しない場合は false を返すようにします。これにより、
do {
} while (next_permutation(ar, n));
のように使うことができます（ここで、n は配列の要素数）。ar の初期配列は、0...N-1 が昇順になった配列です。
引数で与えられた配列より一つ大きな配列は次のようにして得られます。
- 配列を ar[i], i = 0...n - 1 とする
- 配列の中で ar[p - 1] < ar[p] となる p のうち、最も末尾に近いものを探す
- p < q < n - 1 の q の範囲で、ar[p - 1] より大きい数の中で最小値となる ar[q] を探す
- p と q を入れ替える
- p 以降を昇順に並び替える
- ar[p - 1] < ar[p] となる p が存在しなければ、今より大きな配列は存在しない
例を示すと次のようになる
0 1 2 3 // 初期配列
// 2 と 3 が ar[p - 1] < ar[p] となっている
// 2, 3 の中で 2 より大きい最小値は 3
0 1 3 2 // 2 を 3 に入れ替え、それ以降の数を昇順に並べ替える
// 1 と 3 が ar[p - 1] < ar[p] となっている
// 1, 3, 2 の中で 1 より大きい最小値は 2
0 2 1 3 // 1 を 2 に入れ替え、それ以降の数を昇順に並べ替える
// 1 と 3 が ar[p - 1] < ar[p] となっている
// 1 < 3 の 1 と、1 以降で 1 より大きい最小値 3
0 2 3 1 // を入れ替えてその後を昇順に並び替える
// 2 < 3 の 2 と、2 以降で 2 より大きい最小値 3
0 3 1 2 // を入れ替えてその後を昇順に並び替える
// 1 < 2 の 1 と、1 以降で 1 より大きい最小値 2
0 3 2 1 // を入れ替えてその後を昇順に並び替える
// 0 < 3 の 0 と、0 以降で 0 より大きい最小値 1
1 0 2 3 // を入れ替えてその後を昇順に並び替える
1 0 3 2 // 0 < 3、0 以降で 0 より大きい最小値は 2
1 2 0 3 // 0 < 3、0 以降で 0 より大きい最小値は 3
1 2 3 0 // 2 < 3、2 以降で 2 より大きい最小値は 3
1 3 0 2
1 3 2 0
2 0 1 3
2 0 3 1
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0
3 0 1 2
3 0 2 1
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0 // x[p - 1] < x[p] となる p が存在しない→終了
実装
「p と q を入れ替えて、p + 1 以降を昇順に並び替える」をコードに実装して見ました。
public boolean next_permutation(ArrayList<Integer> ar, int n) {
ArrayList<Boolean> used =
new ArrayList<>(Collections.nCopies(n, true));
// find position p at 2 elements in ascending while unuse number
int p = n - 1;
used.set(ar.get(p), false);
while (ar.get(p - 1) > ar.get(p)) {
p--;
if (p == 0) return false; // no 2 elements in ascending
used.set(ar.get(p), false);
}
// find number least but greater than element at p - 1
int leastGreater = ar.get(p - 1) + 1;
while (used.get(leastGreater)) leastGreater++;
// exchange element at p - 1 and least but greater than at p - 1
used.set(ar.get(p - 1), false); // unuse number at p - 1
used.set(leastGreater, true); // use least greater than at p - 1
ar.set(p - 1, leastGreater);
// set unused number in ascending order into array
int j = 0;
for (int i = p; i < n; i++) {
while (used.get(j)) j++; // pick from unused in ascending
ar.set(i, j); // set into array
used.set(j, true);
}
return true;
}
コードの説明です。
- ArrayList unused で、昇順に並び替える数を管理します
- まず、配列の末尾から前後２つの値が昇順になっている場所 p を探します
- どこも昇順になっていなければ、今の配列より大きさが大きい配列はないので終了します
- p の後方にある数の中から、p の前側の値より大きい数の中で最小の値（leastGreater）を探します
- 見つけた値（leastGreater）と p の前側の値を入れ替えます
- p 以降の値を昇順に元の配列に格納していきます
ポイントは、
- 昇順になっている点の値より大きい値の中で、最小の値を探す
- 配列を昇順に並べ替える
だと思いますが、これを、ArrayList<Boolean> used を使うことで解決しています。
next_permutation では配列の要素の値は 0...N - 1 であることから、要素数 N の配列を用意しておくことで管理できます。要素は昇順に並んでいるので、この要素を 0 から昇順に見ていくことで、未使用の数を昇順に見つけることができます。
実際に使ってみる
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Integer> ar = new ArrayList<>();
for (int i = 0; i < n; i++)
ar.add(i);
Main f = new Main();
do {
for (int i = 0; i < n; i++)
System.out.print(ar.get(i) + " ");
System.out.println();
} while (f.next_permutation(ar, n));
}
public boolean next_permutation(ArrayList<Integer> ar, int n) {
/* 上述 */
}
}
出力結果は、
4
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1
1 0 2 3
1 0 3 2
1 2 0 3
1 2 3 0
1 3 0 2
1 3 2 0
2 0 1 3
2 0 3 1
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0
3 0 1 2
3 0 2 1
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0
となりました。