はじめMath! Javaでコンピュータ数学

第34回集合の数学 部分集合、空集合 [後編]

今回は、前回学習した集合の概念を、Java言語で記述するとどうなるか具体的に取り組んでみましょう。手を動かすと、頭で考えているうちは見えてこなかった、解決すべき問題点が見えてくるものです。それらの問題点を解決していくことで、実際的なノウハウ・スキルが身に付いていきます。多少煩雑な演習問題ですが、じっくり取り組んでみてください。

問題:集合Aに対して、集合Bが真部分集合か、部分集合か、一致する要素がないか を確認するプログラムを完成してください。

配列とArrayListでそれぞれ作成してみましょう。以下に判定部分のコードを除いたものを掲載します。目的の処理を行うコードを書き足してください。

ソースコード:HairetsuDeBubunShugoHantei.javaの未完成版
01: //サンプルコード
02: //部分集合・真部分集合の判定
03: //filename : HairetsuDeBubunShugoHantei.java
04: 
05: class HairetsuDeBubunShugoHantei {
06:   public static void main(String[] args) {
07:     char a[] = {’a’,’b’,’c’,’d’,’e’};
08: // char b[] = {’b’,’d’,’a’,’c’,’e’}; //部分集合、かつ等価な集合
09:     char b[] = {’a’,’b’,’c’}; //真部分集合
10: // char b[] = {’a’,’b’,’c’,’f’}; //重複部分のある集合
11: // char b[] = {’x’,’y’,’z’}; //一致する部分のない集合
12: 
13:     //-------------------------------------------------
14:     //判定し、結果を表示するコードをここに書きましょう。
15:     //-------------------------------------------------
16: 
17:   }// end of main
18: }// end of class HairetsuDeBubunShugoHantei
ソースコード:ArrayListDeBubunShugoHantei.javaの未完成版
01: //サンプルコード
02: //部分集合・真部分集合の判定
03: //filename : ArrayListDeBubunShugoHantei.java
04: import java.util.ArrayList;
05: 
06: class ArrayListDeBubunShugoHantei {
07:  public static void main(String[] args) {
08: 
09:     //初期化
10:     ArrayList A = new ArrayList(); //集合A
11:     char a[] = {’a’,’b’,’c’,’d’,’e’};
12:     for (int i = 0 ; i 
13:         A.add( Character.toString(a[i]) );
14:     ArrayList B = new ArrayList();//集合B
15: // char b[] = {’b’,’d’,’a’,’c’,’e’}; //部分集合、かつ等価な集合
16:     char b[] = {’a’,’b’,’c’}; //真部分集合
17: // char b[] = {’a’,’b’,’c’,’f’}; //重複部分のある集合
18: // char b[] = {’x’,’y’,’z’}; //一致する部分のない集合
19:     for (int i = 0 ; i 
20:         B.add( Character.toString(b[i]) );
21: 
22:     //---------------------------------------------
23:     //A に対してB が部分集合か、真部分集合かを判定し、
24:     //結果を表示するコードをここに書きましょう。
25:     //---------------------------------------------
26: 
27:   }// end of main
28: }// end of class ArrayListDeBubunShugoHantei

解説

それぞれのプログラムの完成版を紹介します。この他により効果的なアルゴリズムが考えられるでしょうから、⁠より短く、わかりやすいコード」を目指して奮闘してみてください。

配列版もArrayList版もソースコードでは、集合Aと集合Bの要素を逐一比較し、一致する要素をカウントアップしています。ソースコードでは、配列版の13行目から22行目まで、ArrayList版の22行目から26行目までです。ArrayList版の要素チェック部分のコードがずいぶんシンプルであることに注目してください。

次の図34.1のように判定の基準を設けて処理しています。

図34.1 真・部分・重複・一致なしの判定のしかた
図34.1 真・部分・重複・一致なしの判定のしかた

この図34.1によれば、次のような条件式が考えられます。

真部分集合であるときの条件式は次の通り。

XOR(排他的論理和)をとりますから、要素数の比較は必要なくなりますので、解答例のソースコードには反映していません。

次に部分集合である場合。既に真部分集合である場合が除外されているとすると、あとは一致する集合の場合のみですから、次のような条件式になります。

こののちに、重複する要素の数がない場合、一部重複する集合の場合などを判定しています。実際のソースコードと見比べて、間違いなく判定されているかどうか確認してみてください。

ソースコード:HairetsuDeBubunShugoHantei.javaの完成版
01: //サンプルコード
02: //部分集合・真部分集合の判定
03: //filename : HairetsuDeBubunShugoHantei.java
04: 
05: class HairetsuDeBubunShugoHantei {
06:   public static void main(String[] args) {
07:     char a[] = {’a’,’b’,’c’,’d’,’e’};
08: // char b[] = {’b’,’d’,’a’,’c’,’e’}; //部分集合、かつ等価な集合
09:     char b[] = {’a’,’b’,’c’}; //真部分集合
10: // char b[] = {’a’,’b’,’c’,’f’}; //重複部分のある集合
11: // char b[] = {’x’,’y’,’z’}; //一致する部分のない集合
12: 
13:     //A とB の関係確認
14:     int match = 0;
15:     for( int i = 0;i<a.length;i++){
16:       for( int j = 0;j<b.length;j++){
17:         if (a[i] == b[j]){
18:           ++match;
19:           break;
20:         }
21:       }
22:     }
23:     //結果表示
24:     if (match == a.length ^ match == b.length){
25:       System.out.println("真部分集合です。");
26:     } else if (a.length == b.length && match == a.length) {
27:       System.out.println("部分集合です。");
28:     } else if (match == 0) {
29:       System.out.println("一致する要素はありません。");
30:     } else
31:       System.out.println("重複部分のある集合です。");
32: 
33:   }// end of main
34: }// end of class HairetsuDeBubunShugoHantei
ソースコード:ArrayListDeBubunShugoHantei.javaの完成版
01: //サンプルコード
02: //部分集合・真部分集合の判定ArrayList 版
03: //filename : ArrayListDeBubunShugoHantei.java
04: import java.util.ArrayList;
05: 
06: class ArrayListDeBubunShugoHantei {
07:  public static void main(String[] args) {
08: 
09:     //初期化
10:     ArrayList A = new ArrayList(); //集合A
11:     char a[] = {’a’,’b’,’c’,’d’,’e’};
12:     for (int i = 0 ; i 
13:         A.add( Character.toString(a[i]) );
14:     ArrayList B = new ArrayList();//集合B
15: // char b[] = {’b’,’d’,’a’,’c’,’e’}; //部分集合、かつ等価な集合
16:     char b[] = {’a’,’b’,’c’}; //真部分集合
17: // char b[] = {’a’,’b’,’c’,’f’}; //重複部分のある集合
18: // char b[] = {’x’,’y’,’z’}; //一致する部分のない集合
19:      for (int i = 0 ; i 
20:          B.add( Character.toString(b[i]) );
21: 
22:     //A とB の関係確認
23:     int match = 0;
24:     //一致する要素の数をカウントする
25:     for (int i = 0 ; i 
26:       if ( A.contains( B.get(i) ) == true ) ++match;
27:     //結果の表示
28:     if (match == A.size() ^ match == B.size()){ // 真部分集合
29:       System.out.println("真部分集合です。");
30:     } else if (match == A.size() && A.size() == B.size() ) {
31:       System.out.println("部分集合です(等しい集合です)。");
32:     } else if (match == 0){
33:       System.out.println("一致する要素はありません。");
34:      } else
35:        System.out.println("重複部分のある集合です。");
36: 
37:   }// end of main
38: }// end of class ArrayListDeBubunShugoHantei

今回はここまで

演習問題はいかがでしたか?解説に示したコードはシンプルなものですが、そこに至るためにはいくつか煩雑な論理の整理手続きを必要としました。文章で表していることをコードに移すというのは、意外と大変だということがご理解いただけたのではないでしょうか。

おすすめ記事

記事・ニュース一覧