C++: べき集合の要素を数え上げる

べき集合というものがあります。部分集合の集合というものなんですが、べき集合の要素を出力するプログラムを書いてみました。

原理は簡単です。要素が n 個あるとして、含まれる場合を１、含まれない場合を０とすると

0 0 0
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
0 1 1
1 1 1

これで完全な数え上げとなります。シフト演算子とか論理ANDとかを使うと、要素の数え上げができるわけですね。

では｛ドイツ、フランス、英国｝という集合を考えてみましょう。べき集合はこんなふうです。

{ }
{ Germany }
{ France }
{ Germany France }
{ United Kingdom }
{ Germany United Kingdom }
{ France United Kingdom }
{ Germany France United Kingdom }

すべてのケースを考えるというのはこの小さな集合だけでも大変ですね。

じゃあ、もう少し増やしてみましょう。イタリアとオランダ、スペインを加えてみました。

{ }
{ Germany }
{ France }
{ Germany France }
{ United Kingdom }
{ Germany United Kingdom }
{ France United Kingdom }
{ Germany France United Kingdom }
{ Italy }
{ Germany Italy }
{ France Italy }
{ Germany France Italy }
{ United Kingdom Italy }
{ Germany United Kingdom Italy }
{ France United Kingdom Italy }
{ Germany France United Kingdom Italy }
{ Netherlands }
{ Germany Netherlands }
{ France Netherlands }
{ Germany France Netherlands }
{ United Kingdom Netherlands }
{ Germany United Kingdom Netherlands }
{ France United Kingdom Netherlands }
{ Germany France United Kingdom Netherlands }
{ Italy Netherlands }
{ Germany Italy Netherlands }
{ France Italy Netherlands }
{ Germany France Italy Netherlands }
{ United Kingdom Italy Netherlands }
{ Germany United Kingdom Italy Netherlands }
{ France United Kingdom Italy Netherlands }
{ Germany France United Kingdom Italy Netherlands }
{ Spain }
{ Germany Spain }
{ France Spain }
{ Germany France Spain }
{ United Kingdom Spain }
{ Germany United Kingdom Spain }
{ France United Kingdom Spain }
{ Germany France United Kingdom Spain }
{ Italy Spain }
{ Germany Italy Spain }
{ France Italy Spain }
{ Germany France Italy Spain }
{ United Kingdom Italy Spain }
{ Germany United Kingdom Italy Spain }
{ France United Kingdom Italy Spain }
{ Germany France United Kingdom Italy Spain }
{ Netherlands Spain }
{ Germany Netherlands Spain }
{ France Netherlands Spain }
{ Germany France Netherlands Spain }
{ United Kingdom Netherlands Spain }
{ Germany United Kingdom Netherlands Spain }
{ France United Kingdom Netherlands Spain }
{ Germany France United Kingdom Netherlands Spain }
{ Italy Netherlands Spain }
{ Germany Italy Netherlands Spain }
{ France Italy Netherlands Spain }
{ Germany France Italy Netherlands Spain }
{ United Kingdom Italy Netherlands Spain }
{ Germany United Kingdom Italy Netherlands Spain }
{ France United Kingdom Italy Netherlands Spain }
{ Germany France United Kingdom Italy Netherlands Spain }

そうですね。どのような通商交渉が成り立つでしょうか。

では極め付け、EUが存在しないと仮定して、EU加盟国の各国のそれぞれ組み合わせを考えたとします。

と、書きだそうとするとファイルの大きさがギガを超えてきたのでギブアップです。

組み合わせを考えるとなんと 268435456 となります。

これを考えるとEUのフレームワークってのは偉大ですね。

あらたな世界秩序ってのをつくろう、ってのは無謀じゃないでしょうか。

	#include <iostream>
	using namespace std;
	int main()
	{
	string set[]={
	"Germany",
	"France",
	"United Kingdom",
	"Italy",
	"Netherlands",
	"Spain"
	};
	/*
	string set[]={
	"Austria",
	"Belgium",
	"Bulgaria",
	"Croatia",
	"Cyprus",
	"Czech Republic",
	"Denmark",
	"Estonia",
	"Finland",
	"France",
	"Germany",
	"Greece",
	"Hungary",
	"Ireland",
	"Italy",
	"Latvia",
	"Lithuania",
	"Luxembourg",
	"Malta",
	"Netherlands",
	"Poland",
	"Portugal",
	"Romania",
	"Slovakia",
	"Slovenia",
	"Spain",
	"Sweden",
	"United Kingdom"
	};
	*/
	int n=sizeof(set)/sizeof(set[0]);
	for(int i=0;i<(1<< n);i++)
	{
	cout << "{ ";
	for(int j=0;j<n;j++)
	{
	if(((i>>j)&1)==1)
	{
	cout << set[j] << " ";
	}
	}
	cout <<"}"<< endl;
	}
	return 0;
	}

view raw powerset.cpp hosted with ❤ by GitHub