4

有名な「セットのサブセット」問題を実装しています。うまく機能するソリューションが得られたと思いますが、重複が含まれています。私は list.unique() が状況を引き継ぐことを望んでいましたが、セットに対して == 演算子が定義されていないため、機能しません。セットのセットでも状況は修正されません (現在、セットのリストを使用しています)。

80% の完全なソリューションが得られたので、私が持っていたものよりも優れたアルゴリズムがそこにあることに気付きました。しかし、アルゴリズムを完全に書き直さずに重複を削除する賢い方法があるかどうか疑問に思っていますか?

これが私のコードです：

メイン.CPP:

#include "random.hpp"

using namespace std;

int main(void) {

    subsets2();

    getchar();
    return 0;
}

ランダム.Cpp:

void getSubsets2(set<int> myset, list<set<int> > * ptr, int length) {

    if (length == 1) {
        ptr->push_back(myset);
    }

    else {
        set<int> second(myset);
        set<int>::iterator it;
        ptr->push_back(myset);

        it = myset.begin();
        myset.erase(it);
        it = second.begin();
        ++it;
        second.erase(it);

        getSubsets2(myset, ptr, length - 1);
        getSubsets2(second, ptr, length - 1);
    }
}

void subsets2(void) {
    const int N = 4;
    int myints[N] = {
        88, 33, 23, 22
    };
    set<int> myset(myints, myints + N);
    set<int> set2;

    list<set<int> > mylist;

    list<set<int> > * ptr;
    ptr = & mylist;

    list<set<int> > ::iterator it;
    set<int>::iterator it2;

    getSubsets2(myset, ptr, N);
    mylist.unique();


    for (it = mylist.begin(); it != mylist.end(); ++it) {
        set2 = * it;
        for (it2 = set2.begin(); it2 != set2.end(); ++it2) {
            cout << * it2 << " ";
        }
        cout << "\n";
    }

}

出力：

        22 23 33 88
        23 33 88
        33 88
        88
        33
        23 88
        88
        23
        22 33 88 
        33 88
        88
        33
        22 88
        88
        22
4

3 に答える 3

3

Unique() はconsecutive、コンテナからすべての重複要素を削除します。したがって、unique() を実行する前に、最初に mylist をソートする必要があります。

   mylist.sort();
   mylist.unique();
于 2012-12-21T01:03:50.173 に答える
1

これを行う別の方法と同様に、std::less<T>はすべての標準コンテナーに対して定義されています。したがって、次のように定義できます。

std::set<std::set<int>, std::less<std::set<int>>> set_of_sets;

これにより、重複するセットが自動的に除外されます。完全な例:

#include <set>
#include <vector>
#include <iostream>
#include <functional>

int main()
{
    std::vector<std::vector<int>> x = {{1,2,3}, {1,2}, {1,2,3}, {4,5,6},
                                       {4,5}, {5,6}, {4,5,6}};
    std::set<std::set<int>, std::less<std::set<int>>> set_of_sets;

    for(auto it = x.begin(); it != x.end(); ++it) {
        std::set<int> s;
        s.insert(it->begin(), it->end());
        set_of_sets.insert(s);
    }

    for(auto it = set_of_sets.begin(); it != set_of_sets.end(); ++it) {
        std::cout << "{";
        for(auto it2 = it->begin(); it2 != it->end(); ++it2) {
            std::cout << *it2 << ", ";
        }
        std::cout << "}\n";
    }

    return 0;
}
于 2012-12-21T01:10:14.513 に答える
1

文字列リストを使用して最終結果を保存する:

    list<string> uniq_list;
    for (it = mylist.begin(); it != mylist.end(); ++it) {
        set2 = * it; 
        stringstream ss; 
        for (it2 = set2.begin(); it2 != set2.end(); ++it2) {
            ss << * it2 << " ";
        }
        uniq_list.push_back(ss.str());
    }   
    uniq_list.sort();
    uniq_list.unique();
    for (list<string>::iterator it=uniq_list.begin(); it != uniq_list.end(); it++){
      cout << *it << endl;
    }
于 2012-12-21T01:10:48.103 に答える