C＃によるアルゴリズムとデータ構造

７．集合
７．１集合とは
［集合と要素］
関東の都道府県
群馬県
栃木県
埼玉県
神奈川県
茨城県
東京都
集合「関東の都道府
県」
千葉県
要素
集合の式表現（１）
［集合の要素］
集合Xが要素2,6を持つとき，以下のように書く。
X = {2, 6}
順序は意味を持たないので，
X = ｛6, 2}
は同じことを示す。
［元として含まれる］
要素 a が集合Xの要素のとき，a はXに属するといい，
a ∈ X または X∋ a
（元として含まれる）
と記述する。
要素 b が集合Xの要素でないとき，
b ∈ X または X∋ b
（元として含まれる）
と記述する。
集合の式表現（２）
［集合の要素数］
要素数が無限大のとき無限集合，要素数の有限のとき有限集合と呼び，
|X| = ∞ ，|X| = n
と書く。
|X| = 0
のとき，空集合と呼び，φで表す。
集合の演算
Ａ∪Ｂ
［和集合］
Ａ
Ｂ
Ａ＝｛1, 2, 3, 5｝, Ｂ＝｛1, 3, 6, 7｝
Ａ∪Ｂ＝｛1, 2, 3, 5, 6, 7｝
Ｂ
Ａ＝｛1, 2, 3, 5｝, Ｂ＝｛1, 3, 6, 7｝
Ａ∩Ｂ＝｛1, 3｝
Ｂ
Ａ＝｛1, 2, 3, 5｝, Ｂ＝｛1, 3, 6, 7｝
Ａ－Ｂ＝｛2, 5｝
Ａ∩Ｂ
［積集合］
Ａ
Ａ－Ｂ
［差集合］
Ａ
７．２配列による集合
すべての要素が同じ型のとき，配列を用いて集合を表現で
きる。
６
４
３
７
２
５
上記のように，順序は任意でよい。
ＣやＣ＋＋では，集合の要素数と配列の要素数を等しくす
る必要があるので，初期化時に動的に確保する必要があ
る。
Ｃ＃では，newキーワードでサイズが決まった時点で配列の
大きさを決める。また，C#では，ギザギザの形の配列を宣
言できるので，他のＣ処理系よりも配列による集合表現が
容易である。
プログラム例
フォーム定義
Name:textBox1
Name:textBox2
Name:button1
Name:button2
Name:button3
Name:button4
Name:button5
Name:listBox1
Name:button6
Name:button7
Name:textBox3
プログラム例 ①データ宣言と表示処理
public int[][] Set = new int[3][];
public void 表示()
{
string S;
listBox1.Items.Clear();
foreach(int[] A in Set)
{
if(A.Length==0) S="[]";
else
{
S="";
foreach(int X in A) S += X.ToString()+", ";
S = "[" + S.Substring(0,S.Length-2)+ "]";
}
listBox1.Items.Add(S);
}
}
プログラム例 ②初期値の設定
private void button1_Click(object sender, System.EventArgs e)
{
Set[0]= new int[3]{1,2,3};
Set[1]= new int[0]{};
Set[2]= new int[4]{4,5,6,7};
表示();
}
プログラム例 ③集合ＳにＸが入っているか
// 集合SにXが入っているかどうか
private bool SetMember(int X, int[] S)
{
for(int i=0;i<S.Length;i++)
if(X==S[i])return true;
return false;
}
private void button2_Click(object sender, System.EventArgs e)
{
int EL=int.Parse(textBox1.Text);
int ID=int.Parse(textBox2.Text);
if(ID>=0 && ID<=2)
MessageBox.Show(SetMember(EL,Set[ID]).ToString());
}
プログラム例 ④要素追加
// 集合SにXを追加
private int[] AddMember(int X,int[] S)
{
if(SetMember(X,S)) return S;
int[] S2=new int[S.Length+1];
for(int i=0;i<S.Length;i++) S2[i]=S[i];
S2[S.Length]=X;
return S2;
}
private void button3_Click(object sender, System.EventArgs e)
{
int EL=int.Parse(textBox1.Text);
int ID=int.Parse(textBox2.Text);
Set[ID]=AddMember(EL,Set[ID]);
表示();
}
プログラム例 ⑤要素削除
// 集合SからXを削除
private int[] DelMember(int X,int[] S)
{
if(!SetMember(X,S))return S;
int[] S2=new int[S.Length-1];
int ii=0;
for(int i=0;i<S.Length;i++)if(S[i]!=X) S2[ii++]=S[i];
return S2;
}
private void button4_Click(object sender, System.EventArgs e)
{
int EL=int.Parse(textBox1.Text);
int ID=int.Parse(textBox2.Text);
Set[ID]=DelMember(EL,Set[ID]);
表示();
}
プログラム例 ⑥和集合
// S1とS2の和集合
private int[] SetUnion(int[] S1,int[] S2)
{
int[] S = S2;
foreach (int EL in S1) S = AddMember(EL,S);
return S;
}
private void button5_Click(object sender, System.EventArgs e)
{
int ID1=int.Parse(textBox2.Text);
int ID2=int.Parse(textBox3.Text);
Set[ID1]=SetUnion(Set[ID1],Set[ID2]);
表示();
}
プログラム例 ⑦積集合
// S1とS2の積集合
private int[] SetIntersection(int[] S1,int[] S2)
{
int[] S = new int []{};
foreach (int EL in S1)
if(SetMember(EL,S2))S = AddMember(EL,S);
return S;
}
private void button6_Click(object sender, System.EventArgs e)
{
int ID1=int.Parse(textBox2.Text);
int ID2=int.Parse(textBox3.Text);
Set[ID1]=SetIntersection(Set[ID1],Set[ID2]);
表示();
}
プログラム例 ⑧差集合
// S1とS2の差集合
private int[] SetDifference(int[] S1,int[] S2)
{
int[] S = new int []{};
foreach (int EL in S1)
if(!SetMember(EL,S2)) S = AddMember(EL,S);
return S;
}
private void button7_Click(object sender, System.EventArgs e)
{
int ID1=int.Parse(textBox2.Text);
int ID2=int.Parse(textBox3.Text);
Set[ID1]=SetDifference(Set[ID1],Set[ID2]);
表示();
}
７．３ビットベクトルによる集合
Maxが小さければ，0，1, 2, …，Max－1を符号なし整数の
ビット位置で示すことで，対応するビットの0，１で集合を表
現することができます。
たとえば，１６個の集合を表現するのに，
以下のような１６ビット長の整数１個で表現できます。
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0 1
0
0
0 1
1
0
1
0
0
1
1
1
0
1
集合演算も，整数同士のビット演算AND，ORで代替するこ
とができます。差集合は，
A－B ＝ A And ( Not B）
とすることができます。
BitArray型
C#では，小型の配列としてBitArrayクラスが用意されており，
ビット演算，ビット位置のセットが簡単にできます。
ここでは，これらをBitArrayクラスを用いた集合演算を示し
ます。
プログラム例
フォーム定義
Name:button2
Name:textBox1
Name:textBox2
Name:button1
Name:button8
Name:lblDsp1
Name:lblDsp2
Name:button3
Name:button4
Name:button5
Name:button9
Name:lblDsp3
Name:button6
Name:button7
プログラム例 ①データ宣言と表示処理
BitArray myBA1 = new BitArray(10,false);
BitArray myBA2 = new BitArray(10,false);
BitArray myBA3 = new BitArray(10,false);
private string Bit列(BitArray A)
{
string S="";
for(int i=0;i<A.Length;i++) {
if(A[i]) S += "1";
else S +="0";
}
return S;
}
private void 表示()
{
lblDsp1.Text=Bit列(myBA1);
lblDsp2.Text=Bit列(myBA2);
lblDsp3.Text=Bit列(myBA3);
}
プログラム例 ②Form1_Load，要素追加，要素削除
private void Form1_Load(object sender, System.EventArgs e)
{
表示(); }
private BitArray AddMember(BitArray BA,int Member)
{
BitArray B=BA;
if(Member < BA.Length) B[Member]=true;
return B;
}
private BitArray DeleteMember(BitArray BA,int Member)
{
BitArray B=BA;
if(Member < BA.Length) B[Member]=false;
return B;
}
プログラム例 ③コマンド処理（その１）
// BA1に要素を追加
private void button1_Click(object sender, System.EventArgs e)
{ myBA1=AddMember(myBA1,int.Parse(textBox1.Text)); 表示(); }
// BA2に要素を追加
private void button2_Click(object sender, System.EventArgs e)
{ myBA2=AddMember(myBA2,int.Parse(textBox2.Text)); 表示(); }
// BA1に要素があるかどうか？
private void button3_Click(object sender, System.EventArgs e)
{ MessageBox.Show(myBA1[int.Parse(textBox1.Text)].ToString()); }
// BA2に要素があるかどうか？
private void button4_Click(object sender, System.EventArgs e)
{ MessageBox.Show(myBA2[int.Parse(textBox2.Text)].ToString()); }
// BA1 Or BA2
private void button5_Click(object sender, System.EventArgs e)
{ BitArray A=(BitArray)myBA1.Clone();
myBA3=A.Or(myBA2);表示();
}
プログラム例 ④コマンド処理（その２）
// BA3 = BA1 And BA2
private void button6_Click(object sender, System.EventArgs e)
{ BitArray A=(BitArray)myBA1.Clone();
myBA3=A.And(myBA2);表示();
}
// BA3 = BA1 - BA2
private void button7_Click(object sender, System.EventArgs e)
{
BitArray A=(BitArray)myBA1.Clone();
BitArray B=(BitArray)myBA2.Clone();
myBA3=A.And(B.Not());表示();
}
// BA1から要素の削除
private void button8_Click(object sender, System.EventArgs e)
{ myBA1=DeleteMember(myBA1,int.Parse(textBox1.Text)); 表示(); }
// BA2から要素の削除
private void button9_Click(object sender, System.EventArgs e)
{ myBA2=DeleteMember(myBA2,int.Parse(textBox2.Text)); 表示(); }

Download Report