集合の表示とその演算

説明:状態の次元数が比較的多いが、各次元数が2つしかない場合は、集合で表すことが考えられる.次に,集合の表現とその演算について説明する.

一、集合の表示及び基本操作

C言語における集合はバイナリコードで表され,集合を整数に符号化することに相当する.式f(S)=Σ2^i(i∈S)を用いて集合を整数に符号化する.次に、セットにn個の要素があり、番号は0から始まると仮定します.

空セット:0

全集:(1<

はi番目の要素の集合のみを含む{i}:1<

i番目の要素が集合{0,1......n-1}:if((S>>i)&1)

に属するか否かを判断する.

集合にi番目の元素S∪{i}:S|=1<を加える.

集合からi番目の元素S{i}:S&~(1<を除去する.

集合SとTの並列集合S∪T:S|T

集合SとTの交差S∩T:S&T

集合Sは全集であり、sはそのサブセットであり、sの補完:s^S

二、列挙サブセット

列挙サブセットは、大きなものから小さいものまでの逆順序列挙を用いることができる(順序列挙には多くの欠陥があるため).全集をSとし,sをSのサブセットとすると,最初はs=Sとし,その後は1回ずつ減算し,減算後はSのサブセットではない可能性があるため,(s−1)&Sをとるべきである.列挙されたコードを書くのは難しくありません.

for (int s = S; s >= 0; s = (s - 1)&S)
	{
		// 
	}

三,列挙集合{0,1......n−1}に含まれるすべてのサイズkのサブセット

辞書順では、最小のサブセットは(1<(1)最低位の1から連続する1の区間を求める、例えば(0101110->0001110)
(2)この区間を全て0にし、区間左側のその0を1にする(0101110->0110000)
(3)最初のステップで取り出した区間を右に移動し、残りの1の個数が1つ減るまで例えば(0001110->0000011)
(4)第2ステップおよび第3ステップの結果をビット単位または(並列化)し、例えば(0110000|0000011=01110011)
上記の手順に従って、以下のようなコードを書くのは難しくなく、一歩一歩の書き方に注意しましょう.

int k,n;
	int s = (1 << k) - 1;
	while (s < 1 << n)
	{
		int x = s&-s;//s&-s 1 ， x
		int y = s + x;// ， s+x ， y
		s = ((s&~y) / x >> 1) | y;//s&~y 1 ， 0， z, (z/x)>>1 ， y ， 
	}