AOJ ITP2 5_D（Permutation Enumuration）を解く

Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の5_D問題をC++で解いてみました。

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#5では、「順列」というテーマで学びます。

#3から#6は、alogrithm をインクルードして利用する機能を紹介します。全てのアルゴリズムは、データ構造の実装から切り離されています。アルゴリズムの要件（主にイテレータ）を満たせば動作します。

問題（5_D: Permutation Enumuration）

問題はリンク先をご覧ください。

AOJ ITP2 5_D問題: Permutation Enumuration

全ての順列を next_permutation を使って生成します。

C++ プログラム例（ITP2 5_D）

next_permutation は、前回の記事で紹介しました。この関数を使って 1 から n までの全ての順列を生成します。

この do-while 文は、すべての順列を生成する定型パターンとなります（18、22行目）。

以下は、C++のプログラムです。

#include <iostream>
#include <algorithm>

#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);

	for (int i = 0; i < n; ++i) {
		a[i] = i + 1;
	}

	do {
		for (int i = 0; i < n; ++i) {
			cout << a[i] << " \n"[i == n - 1];
		}
	} while (next_permutation(a.begin(), a.end()));

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

今回、紹介したコードは、$n!$ 通りの順列の全探索を行う場合に使われます。$n$ の値は非常に速く大きくなるため、$n = 10$ 程度で使われる問題が多いようです。

引き続き、ITP2 の問題を紹介していきます。