70886


和集合のプログラミング実装はC言語の参考書に載っていたので、それを参考にして実行したのですが、積集合のC言語実装の方法がわかりません。

ちなみに、和集合のプログラムは以下のように記述しました。

**C で和集合を求めるプログラム:**

[code]

    #include <stdio.h>
    
    /* size個 のデータが入っている配列を 配列の先頭から順に出力する */
    void printIntArray(int a[], int size)
    {
        int i;
        for(i=0;i<size;i=i+1) {
            printf("%d ", a[i]);
        }
        printf("\n");   
    }
    
    /* na個 のデータが入っている集合に x と等しい要素があるかどうかを判定する \ */
    int memberOf(int x, int a[], int na)
    {
        int i,result=0;
        for(i=0;i<na;i=i+1) {
            if (x==a[i]) {
                result = 1;
            }
        }
        return result;
    }
    
    // 集合a と集合b の和集合を集合c として求める
    // na, nb は，集合a, b の要素数
    // 返り値は，集合c の要素数
    int unionSet(int a[], int na, int b[], int nb, int c[])
    {
        int i, j;
        j=0;
        for(i=0;i<na;i=i+1) {
            if (!memberOf(a[i],b,nb)) {
                c[j]=a[i];
                j=j+1;
            }
        }
        for (i=0;i<nb;i=i+1) {
            c[j]=b[i];
            j=j+1;
        }
        return j;
    }
    
    int main(void)
    {
        int SA[1024] = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18};
        int SB[1024] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int SC[1024] = {};
        int length=unionSet(SA,10,SB,10,SC);
    
        printf("集合A: \n");
        printIntArray(SA, 10);
        printf("集合B: \n");
        printIntArray(SB, 10);
    
        printf("集合A∪ B: \n");
        printIntArray(SC, length);
    
        return 0;
    }
    
[/code]

なお、Haskell での積集合の実装方法は以下のように記述できた思うので、上記プログラムの `unionSet()`
の部分を改変すればいいと思うのですが、どのように改変すべきなのかがよくわかりません。  
ご回答よろしくお願いします。

**Haskell で積集合を求めるプログラム:**

[code]

    memberOf(x,[])=False
    memberOf(x,a:as)=if a==x then True else memberOf(x,as) 
    inter([],bs)=[]
    inter(a:as,bs)=if memberOf(a,bs) then a:inter(as,bs) else inter(as,bs)
    
[/code]


CC BY-SA 4.0
2020-10-01T11:08:15.797
70863
2020-10-02T11:35:48.203
2020-10-02T11:35:48.203
3060
41837
question
c
C言語を用いた積集合を求めるプログラムの実装方法が分からない


和集合 `A ∪ B` や積集合 `A ∩ B` を **効率よく** かつ **安全に**
求めようとすると結構面倒です。提示の参考書サンプルコードはアルゴリズムの解説のために安全性を犠牲にしている様子。そのまま実用に供してはいけません (`SC`
のサイズを渡していないのでバッファーオーバーフロー脆弱性をはらんでいる)

提示コードは片方の全要素をもう片方の全要素中から検索しようとしていて手数 `O(N*N)`
となっており、要素数が増えると極端に遅くなってしまい非効率です。コンテナ（配列）中の要素がソートされているならもっと効率よく求めることができます。イントロソートの手数は
`O(N log N)` であり `O(N*N)` のほうが `O(N log N)` よりはるかに手数が多い（ `N` が大きいとき)
ので、２つの配列をソートしてから積和集合を求めたほうが要素数が多いときは高速になるでしょう。という話を参考書の次の節で解説しているはず。

[c++](/questions/tagged/c%2b%2b "'c++' のタグが付いた質問を表示") では積集合を求めるのに
`<algorithm>` 中に `std::set_intersection()`
という関数テンプレートが用意されています。この関数は元要素がソート済みであることを前提に効率よく積集合を求めてくれます。「積集合を求めること」が目的であるならライブラリ関数をうまく使えば目的が達せられます。

sample code for C++

[code]

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    
    int main()
    {
        int a[] = { 2, 3, 6, 16, 19 };
        int b[] = { 1, 2, 5, 12, 16 };
        std::vector<int> r;
        std::set_intersection(std::begin(a), std::end(a), std::begin(b), std::end(b), std::back_inserter(r));
        std::copy(r.begin(), r.end(), std::ostream_iterator<int>(std::cout, " "));
        std::cout << std::endl;
    }
    
[/code]

結果は `2 16`

* * *

実用上は未ソートの配列の積和集合を取ることは効率面でありえないです（よほど要素数が少ない場合を除く）ソート済み配列の積集合を求めるロジックが知りたいのであれば
`std::set_intersection()` のソースを見てみましょう。手元にあるちょっと古い SGI 版 STL の
`set_intersection()` オイラ流に [c](/questions/tagged/c "'c' のタグが付いた質問を表示")
向けに書き換えてみました。

[code]

    #include <stdio.h>
    int* myset_intersection(const int* b1, const int* e1, const int* b2, const int* e2, int* r) {
        while (b1 != e1 && b2 != e2) {
            if (*b1 < *b2) ++b1;
            else if (*b2 < *b1) ++b2;
            else {
                *r = *b1;
                ++b1, ++b2, ++r;
            }
        }
        return r;
    }
    
    #define elementsof(a) (sizeof(a)/sizeof(0[a]))
    
    int main() {
        int a[] = { 2, 3, 6, 16, 19 };
        int b[] = { 1, 2, 5, 12, 16 };
        int r[10];
        int* q = myset_intersection(a, a+elementsof(a), b, b+elementsof(b), r);
        for (int* p=r; p<q; ++p) printf("%d ", *p);
        printf("\n");
    }
    
[/code]

注意：やはり同じくバッファーオーバーフロー脆弱性をはらんでいますが説明のためにチェック省略 ( STL は `back_inserter` を使う前提)
実用に供するにはどう修正すればよいかは宿題にしておきましょう。

* * *

配列内に同じ要素が複数個ある場合の挙動がどうなってほしいのかは事前に仕様策定しておかなければなりません。 `std::set_intersection()`
は「集合」を扱う前提なので、集合論的には同じ要素が複数個あることは想定していません。


CC BY-SA 4.0
2020-10-02T02:27:43.057
70878
2020-10-02T02:27:43.057
8589
70863
answer


効率良く行うならソートやハッシュを使ったり、安全に行うならライブラリを使用したりすべきですが、  
Cの勉強用にとりあえず動くものを実装したいという事ならば次のようになります。

提示 Haskell コードは `as` が空になるまで順に取り出していき、条件に一致するものを `:`
の左側に集めていく、という発想で書かれていると思います。  
Haskell の考え方ですと「順に取り出していき」ますが、実際のところ「左から順に走査していく」（for文）のと同じです。  
そして集めていくのは和集合の提示コードでやっているように、十分な大きさの配列と、どこまで埋まっているかを記録する変数を用意すればよいと思います。

[code]

    int intersectSet(int a[], int na, int b[], int nb, int c[]) {
        int i, k;
        k = 0;
    
        // a を順に走査
        for (i = 0; i < na; i = i + 1) {
    
            // a[i] が条件を満たすならば
            if ( memberOf(a[i], b, nb) ) {
    
                // c に追加
                c[k] = a[i];
                k = k + 1;
            }
        }
        return k;
    }
    
[/code]

簡単のために `c` の境界チェックを行っていません。実際に使用する場合は追加してください。


CC BY-SA 4.0
2020-10-02T10:35:07.237
70886
2020-10-02T10:35:07.237
20885
70863
answer