順列の全探索アルゴリズムについての備忘録

順列とは

いくつかのものを順序付けて並べることです。例えるなら
「1, 2, 3, 4, 5」も
「3, 5, 1, 4, 2」も
「1, 1, 2, 1, 3」も順列です。

順列における辞書順とは

今回紹介する順列の全探索アルゴリズムは「辞書順における次の順列に変換する」という作業をひたすら繰り返すことで実現します。「1, 2, 3, 4, 5」と5つの数字があるとします。この数字を適当に並べた3つの順列を次に示します。
「12345」「54321」「32415」
この3つの順列を辞書順にすると「12345」「32415」「54321」となります。
12345 < 32415 < 54321
という関係になっていることがわかると思います。
つまり「1, 2, 3, 4, 5」という5つの数字でできた順列における、辞書順で一番若いものは
「1, 2, 3, 4, 5」
と昇順に並べたものであり、次に出てくるのは
「1, 2, 3, 5, 4」
であり、最後に出てくるのは
「5, 4, 3, 2, 1」
と降順に並べたものになります。

辞書順における次の順列に変換するアルゴリズム

先ほど順列の全探索アルゴリズムは「辞書順における次の順列に変換する」という作業をひたすら繰り返すことで実現するということを書きました。よって、辞書順における次の順列に変換するアルゴリズムについて説明します。以降「次の順列」と表現された場合「辞書順における次の順列」という意味です。同様に「最初の順列」や「最後の順列」と表現があった場合、辞書順における順列の最初と最後という意味です。
具体例で見るのがわかりやすいと思うので、次の順列に変換する手順の例を3つ挙げます。

①
昇順の順列「1, 2, 3, 4, 5」を用意します。4と5を入れ替えることで「1, 2, 3, 5, 4」という次の順列に変換できます。

②
では「1, 2, 3, 5, 4」を次の順列「1, 2, 4, 3, 5」に変換する手順を見てみます。「1, 2, 3, 5, 4」を見ると「5, 4」の部分が降順になっていることが分かります。以上より「1, 2, 3, 5, 4」は「1, 2, 3」から始まる最後の順列であることが分かります。つまり「1, 2, 3, 5, 4」の次の順列は「1, 2」から始まり「3」の次に小さい「4」の続いた「1, 2, 4」から始まる順列であることが分かります。「1, 2, 4」から始まる最初の順列は、残りの「3, 5」を昇順にしたものを追加した「1, 2, 4, 3, 5」となります。これで「1, 2, 3, 5, 4」を次の順列「1, 2, 4, 3, 5」に変換することができました。

③
では同様に「3, 1, 2, 5, 4」を次の順列「3, 1, 4, 2, 5」に変換する手順を見てみましょう。「3, 1, 2, 5, 4」を見ると「5, 4」という部分が降順になっていることが分かります。以上より「3, 1, 2, 5, 4」は「3, 1, 2」から始まる最後の順列であることが分かります。つまり「3, 1, 2, 5, 4」の次の順列は「3, 1」から始まり「2」の次に小さい「4」の続いた「3, 1, 4」から始まる順列であることが分かります。「3, 1, 4」から始まる最初の順列は、残りの「2, 5」を昇順にしたものを追加した「3, 1, 4, 2, 5」となります。これで「3, 1, 2, 5, 4」を次の順列「3, 1, 4, 2, 5」に変換することができました。

②と③で行った手順を機械的にまとめてみます。()内に③での具体例を挙げます。また要素番号は0から始まります。

( 1 ) 順列を後ろから確認していったとき、降順ではなくなる要素番号を i とする
(「3, 1, 2, 5, 4」の場合「2」の要素番号2、i = 2)
( 2 ) i + 1 番目以降で i 番目の要素より大きい最小の要素がある場所を要素番号 j とする
(「3, 1, 2, 5, 4」で3番目以降にある「2」より大きい最小の数「4」その要素番号4、j = 4)
( 3 ) i 番目と j 番目の要素を入れ替える
(2番目と4番目を入れ替える「3, 1, 4, 5, 2」)
( 4 ) i + 1 番目以降を昇順に並べ替える
(3番目以降を昇順にする「3, 1, 4, 2, 5」)

このように上記の手順で次の順列に変換することができます。また①に上記の手順を行うことで次の順列に変換することが可能です。
( 1 ) から ( 3 ) までの状態で i + 1 番目以降は降順に並んでいることを考慮すると以下のように表現することができます。

( 1 ) 順列を後ろから確認していったとき、降順ではなくなる要素番号を i とする
( 2 ) i + 1 番目以降の要素を後ろから見ていったときに、初めに現れる i 番目の要素より大きい要素が出てきた場所を要素番号 j とする
( 3 ) i 番目と j 番目の要素を入れ替える
( 4 ) i + 1 番目以降を逆順にする

( 2 ) と ( 4 ) の表現が変わり、より単純なアルゴリズムになりました。また ( 1 ) の時点で要素番号 i が見つからなかった場合、それは降順であり辞書順における最後の順列となります。

ソースコード

以上のことを踏まえJavaでnextPermutationという辞書順における次の順列に変換し、変換出来たらtrueを返すメソッドを作ってみました (このメソッドに関してはいろんなところに転がっています)。

import java.util.Arrays;

public class Permutation {

	// array[i]とarray[j]を入れ替える
	private static void convertArray(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	// array[i]以降を反転する
	private static void reversalArray(int[] array, int i) {
		int j = array.length - 1;
		while (i < j) {
			convertArray(array, i, j);
			i++;
			j--;
		}
	}

	// 辞書順で次の順列にする
	private static boolean nextPermutation(int[] array) {
		// array[i] < array[i + 1]となる最大のiを見つける
		int i = array.length - 2;
		while (0 <= i) {
			if (array[i] < array[i + 1]) {
				break;
			}
			i--;
		}

		// array[i] < array[i + 1]となるiが見つからなければfalse
		if (i < 0) {
			return false;
		}

		// array[i + 1]以降でarray[i]より大きい最小の数array[j]となるjを見つける
		int j = array.length - 1;
		while (i < j) {
			if (array[i] < array[j]) {
				break;
			}
			j--;
		}

		// array[i]とarray[j]を入れ替える
		convertArray(array, i, j);

		// array[i + 1]以降を昇順にする
		reversalArray(array, i + 1);

		// ここまで処理が来ればtrue
		return true;
	}

	public static void main(String[] args) {
		int[] array = { 5, 3, 2, 4, 1 };
		Arrays.sort(array);
		int count = 1;
		do {
			System.out.printf("%5d %s\n", count, Arrays.toString(array));
			count++;
		} while (nextPermutation(array));
	}
}

出力結果は長いのでここには書きませんが、「1, 2, 3, 4, 5」「1, 2, 3, 5, 4」....「5, 4, 3, 2, 1」とすべて表示されます。
今回は以上で終わりたいと思います。ありがとうございました。