AOJ ITP2 11_D（Enumeration of Combinations）を解く

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

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#11では、ビットセットIIとしてbit処理を学びます。

問題（11_D: Enumeration of Combinations）

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

AOJ ITP2 11_D問題: Enumeration of Combinations

n個からk個選ぶ組み合わせを列挙します。

考え方

5_D で学んだ next_permutation を使います。5_D では、異なる値を含む配列を与えました。今回は、n個の配列にk個の0と (n-k) 個の1を設定します。

next_permutation は、複数同じ値があってもうまく動きます。

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

考え方で述べたようにk個の0と (n-k) 個の1を設定した配列を用意します（15ー21行目）。next_permutation を使って順列の値を次々と生成します。

配列の0がある場所を出力していけば、目的の組み合わせをひとつ得ることができます。

注意としては、next_permutation は、ビット順になるため、整数値の順になりません。このため map に格納して、後で整数値順に出力します（36ー42行目）。

以下が、C＋＋プログラムとなります。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

typedef unsigned long long int ull;

int main()
{
	int n, k;
	cin >> n >> k;

	vector<int> p(n);
	for (int i = 0; i < k; ++i) {
		p[i] = 0;
	}
	for (int i = k; i < n; ++i) {
		p[i] = 1;
	}

	map<int, vector<int>> m;
	do {
		int num = 0;
		vector<int> subset;
		for (int i = 0; i < n; ++i) {
			if (p[i] == 0) {
				num += (1ULL << i);
				subset.push_back(i);
			}
		}
		m[num] = subset;
	} while(next_permutation(p.begin(), p.end()));

	for (auto e : m) {
		cout << e.first << ":";
		for (int i = 0; i < (e.second).size(); ++i) {
			cout << " " << (e.second)[i];
		}
		cout << endl;
	}

	return 0;
}

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

最後に

今回で、「プログラミング応用」（ITP2）が提供している全44問を解くことができました。

ITP2 は、C++ で用意されている標準ライブラリを題材としています。Vector や map などのコンテナから、幅広いアルゴリズムの実装を学べました。このコースで始めた知ったライブラリ関数もあり、勉強になりました。

ITP1 と同じお礼となりますが、良質なコンテンツを無料で公開していただいている会津大学に感謝いたします。