AOJ ITP2 5_C（Permutation）を解く

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

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

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

問題（5_C: Permutation）

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

AOJ ITP2 5_C問題: Permutation

順列を生成する next_permutation と prev_permutation について学びます。

std::next_permutation について

以下は、cpprefjp 様の記事を参考にさせていただきました。

std::next_permutation は、与えられたイテレータ範囲を順列として、辞書順による次の順列を生成します。

  template <class BidirectionalIterator>
  bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);    

次の順列が存在する場合は、true を返し、存在しない場合は、false を返します。

最大で (last1 – first1)/2 回の swap を行います。

std::prev_permutation について

以下は、cpprefjp 様の記事を参考にさせていただきました。

std::prev_permutation は、与えられたイテレータ範囲を順列として、辞書順による前の順列を生成します。

  template <class BidirectionalIterator>
  bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

前の順列が存在する場合は、true を返し、存在しない場合は、false を返します。

最大で (last1 – first1)/2 回の swap を行います。

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

順列を受け取り、前の順列を prev_permutation で求めて出力します。受け取った順列を出力した後、次の順列を next_permutation で求めて出力します。

前の順列を求めるときに受け取った数列の値を書き換えます。そのため、受け取った順列のコピーを prev_permutation に渡しています。

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

#include <iostream>
#include <algorithm>

#include <vector>

using namespace std;

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

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

	if (prev_permutation(p.begin(), p.end())) {
		for (int i = 0; i < n; i++) {
			cout << p[i] << " \n"[i == n - 1];
		}
	}

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

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

	return 0;
}

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

最後に

C で順列を生成する関数が必要な場合、自作していました。C++ では、この記事で紹介した関数を使っています。

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