順列全探索について

今回は再びAtCoderの記事。
いよいよAtCoder Beginner Contest 163が近づいてきたので、AtCoderの勉強をしてました。
前回のbit全探索に続いて、今回は「順列全探索」です。
ちなみに、前回のAtCoderの記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

順列全探索とは

決まった数字や文字の列のすべての順列を洗い出す方法のこと。
すべての並び方を用いて何かしたいときに使います。
全部でn!通りあるので、nが大きくなると使えません。
問題の見分け方は、bit全探索よりも簡単かなと思いました。

どのように解くのか（Javaの場合）

基本的に競プロの参加者はC++を使っているので、std::next_permutationが使えます。
これは辞書順で次の順列を返してくれる便利なものです。
しかしこれはJavaにはありません。
ないので、仕方なく自作します。
他のサイトを参考にして作ったのがこちらです。
（ついでに、階乗も作りました。いらないとは思いますが、念のため。）

//階乗
static int factorial(int n) {
	if(n == 0)
		return 1;

	return n * factorial(n-1);
}

//次の順列を生成する
static boolean next_permutation(int[] array, int start, int end) {

	if(array == null || start > end || start < 0 || end > array.length) {
		System.out.println("Error: 引数が正しくありません。");
		return false;
	}

	for(int i=end-2; i>=start; i--) {
		if(array[i] < array[i+1]) {
			int j = end - 1;
			while(array[i] >= array[j]) {
				j--;
			}

			//swap
			int tmp = array[j];
			array[j] = array[i];
			array[i] = tmp;

			Arrays.sort(array, i+1, end);

			return true;
		}
	}

	return false;
}

このnext_permutationを呼び出すことで次の順列を呼び出せます。
具体的には、次のように使います。

//順列全探索
for(int i=0; i<factorial(n); i++) {
	//ここに問題に応じた処理を入れる
	
	next_permutation(array, 0, array.length);
}

なぜこれで解けるのか

こちらのサイトがわかりやすいです。C++ですが、こちらのサイトを参考にして上のライブラリを作りました。
qiita.com

というわけで、今回は順列全探索の勉強でした。
ひとまずこれで全探索の勉強は終わりです。
bit全探索もそうですが、こういうのは知らないと絶対解けないですよね。
こちらのサイトによれば、これで茶色コーダーになるための勉強はひとまず終わりのようです。
（この方は高校生でレッドコーダーまで行っていてすごいですよね。若いってうらやましい。）
qiita.com
ですが、これだけではD問題は解けないと思うので、次はBFS/DFSを勉強したいと思います。
これから、地道に勉強していくので、応援よろしくお願いします。