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

第35回集合の数学 和集合・積集合

韓国を訪れた際、仏教寺院建築を見ると、色彩こそ異国情緒を感じますが、建物の雰囲気はとてもよく似ていました。ご近所さんなのだ、ということを強く感じました。アジアの文化はどれも違っているようでどこか似ています。違いは何で、共通するところは何か、そう考えるのは、今回の和集合・積集合の数学と共通するように思われます。さて、考え方を数学的に切り替えて、今回の集合の数学に取り組んで行きましょう。

図35.1 相違と共通点から技を学ぶ
図35.1 相違と共通点から技を学ぶ

和集合

和集合とは

和集合とは、二つの集合を「もれなく」⁠だぶりなく」ひとつにまとめる演算です。集合Aと集合Bの和集合はA∪Bと書きます。⁠エー・カップ・ビー」と読みます[1]⁠。図35.2(a)にオイラー図を用いた和集合の演算例を示します。

和集合の記号∪と全体集合の記号Uはよく似ているので紛らわしく見えます。手で書く際には全体集合の記号Uの開いた側を釘の頭のようにつぶして書くと良いでしょう。

図35.2 和集合とは
図35.2 和集合とは

和集合の要素数

図35.2を詳しく見ましょう。

和集合演算は二つの集合を「もれなく」⁠だぶりなく」ひとまとめにします。ですから、図35.2(a)のような場合、集合Aに含まれている数3、4、5と集合Bに含まれていた3、4、5はだぶります。和集合を取ったあと、どちらかに含まれていた3、4、5を捨てなければなりません。AとBで重複する要素は片方を無視し一つと数えるのです。このため、n(A)=5、n(B)=5なのですが、重複が3ありますので、n(A∪B)=7となります。単純に、5+5=10とならないので注意が必要です。

和集合と現実問題

コンピュータを用いたデータ処理に当てはめて考えてみましょう。別々に収集された二つのデータの集合から、重複する部分を取り除いて効率よくデータを集積したいという場合に相当します。カードのコレクションをしている人が重複するカードを持っていると、一つだけ残して他を処分してしまうような事ですね。好きなアイドルのカードなら、同じのが何枚あってもかまわない?それは趣味の問題。人の感情は数学で処理出来ませんという現実問題。許してあげましょう。

ともあれ、重複を取り除いて一つの集合にまとめるという操作は、次の式35.1のように書くことが出来ます。

≡は「定義」を意味します。プログラマは、右から左へ値を「代入」する習慣がありますから、次の式35.2のように書くこともあります。

今回の例の場合は、集合AとBの要素の様子が図35.2(b)のようになっていました。ハッチングした部分(斜線で埋めた部分)が和集合の演算結果を表しています。和集合が常にこのような関係にあるとは限りません。二つの集合の要素の様子は図35.2(c)から(d)のようにいくつかの場合が考えられます。プログラミング言語で和集合の処理を行う場合には、それぞれの場合を意識した処理を心がけましょう。単純に配列やコレクションクラスを連結してハイおしまい!と出来ないのです。

積集合

積集合とは

積集合とは、二つの集合から共通部分を取り出す演算です。集合Aと集合Bの積集合はA∩Bと書きます。⁠エー・キャップ・ビー」と読みます[2]図35.3(a)にオイラー図を用いた積集合の演算例を示します。

図35.3 積集合とは
図35.3 積集合とは

積集合の要素数

集合AとBが図35.3(a)のような関係にある時の積集合の結果は、右端のように要素数n(A∩B)=3となります。図35.3(b)のように、ハッチングして示すことも出来ます。

和集合の時と同様、二つの集合の要素がどのような様子かによって、図35.3(c)から(e)のように図が異なります。

積集合と現実問題

CADのデータをメモリに読み込み、線分を追加し、再び保存するという場合を例にとりましょう。追加されたデータのみを保存すれば、処理時間もデータのサイズも節約できます。このような場合に、変更前の図面データと変更後の図面データで積集合をとり、結果のみを追加で保存すれば無駄なく効率が良くなります。

問題:集合とJava言語に関する以下の問いに答えてください。

(1)二つの集合の和集合をとり、結果を表示するプログラムを作りましょう。集合の格納には配列を用いてください。

(2)二つの集合の積集合をとり、結果を表示するプログラムを作りましょう。集合の格納にはArrayListを用いてください。

解説

(1)二つの集合の和集合をとり、結果を表示するプログラムを作りましょう。集合の格納には配列を用いてください。

和集合演算を配列を用いて行ってみます。MAX_LENGTHとして配列長の最大値を仮定し、和集合の結果を代入する配列をMAX_LENGTHほど確保しています。Java言語の配列は一度宣言するとサイズを変更できませんから、あらかじめ必要なだけ確保しなければなりません。これが配列の不便なところです。

ソースコード:HairetsuDeWashugo.java
//サンプルコード
//和集合をとる
//filename : HairetsuDeWashugo.java

class HairetsuDeWashugo {

  static final int MAX_LENGTH = 255; //配列長の最大値

  public static void main(String[] args) {

    int a[] = {1,2,3,5,8}; //集合a
    int b[] = {2,4,5,7,9}; //集合b 重複あり
//    int b[] = {4,7,9,10,13}; // 重複なし
//    int b[] = {2,5}; // a はb を包含する
//    int b[] = {1,2,3,4,5,7,8}; // bはaを包含する
    int c[] = new int[MAX_LENGTH]; //集合c
    int nElementsC = 0; //集合c の要素数
    //C <- A cup B
    System.arraycopy(a,0,c,0,a.length); //配列のコピー。便利。
    nElementsC = a.length;
    boolean match = false;
    for( int i=0; i<b.length ; ++i){
      for( int j=0; j<a.length; ++j){
        if (b[i] == a[j]){
          match = true;
          break;
        }
      }
      if (match == false) {
        c[nElementsC]=b[i];
        ++nElementsC;
      }
      match = false;
    }
    //結果表示
    for( int i = 0 ; i < nElementsC; ++i ){
      System.out.println("c["+i+"]=" + c[i]);
    }
  }// end of main
}// end of class HairetsuDeWashugo

(2)二つの集合の積集合をとり、結果を表示するプログラムを作りましょう。集合の格納にはArrayListを用いてください。

積集合演算をArrayListを用いて行います。

ソースコード:ArrayListDeSekishugo.java
//サンプルコード
//積集合をとる ArrayList 版
//filename : ArrayListDeSekishugo.java

import java.util.ArrayList;

class ArrayListDeSekishugo {
  public static void main(String[] args) {
    //集合A の宣言と初期化
    ArrayList<Integer> A = new ArrayList<Integer>();
    int a[] = {1,2,3,5,8};
    for (int i = 0 ; i < a.length ; ++i ) A.add( a[i] );
    //集合B の宣言と初期化
    ArrayList<Integer> B = new ArrayList<Integer>();
    int b[] = {2,4,5,7,9}; //集合b 重複あり
// int b[] = {4,7,9,10,13}; // 重複なし
// int b[] = {2,5}; // a はb を包含する
// int b[] = {1,2,3,4,5,7,8}; // b はa を包含する
    for (int i = 0 ; i < b.length ; ++i ) B.add( b[i] );
    //集合C の宣言
    ArrayList<Integer> C = new ArrayList<Integer>();
    //C <- A cap B
    for( Integer i : A ) {
      if ( B.contains( i ) ) C.add(i);
    }
    //結果表示
    for( int i = 0 ; i < C.size() ; ++i ){
      System.out.println("C.get("+i+")=" + C.get(i) );
    }
  }// end of main
}// end of class ArrayListDeSekishugo

ArrayListを用いると、変数の宣言に少々行数を取りましたが実行部分が劇的にシンプルになります。今回For-each構文を用いてみました。for(Integer i:A){の部分で、ArrayListAの要素を変数iに取ってきます。続くループのブロックでは、iにAの最初の要素が入っています。一回目のループが終了すると、iにはAの次の要素が入ります。単純なForループを使った場合と、大きな違いを感じられないかもしれませんが、

  • (a)ループのブロック中でA.get(i)として要素を呼び出す代わりに、
  • (b)単純にiだけで済ませられるという利点があります。

(a)の場合のiはカウンタで、1,2,3,・と続く添字の役割をしています。対する(b)のiは、ArrayListAの要素そのものです。

慣れが必要ですが、場合によっては大変便利です。良い例が、このソースコードの続く部分です。こちらでは、演算の結果を格納したCの内容を全て表示します。For-Eachループを用いても良いのですが、⁠C.get(1)=2⁠などと表示したかったので、ここではカウンタ用変数を用いたForループの方が無駄がないと思われます。

おすすめ記事

記事・ニュース一覧