집합 목록에서 중복 제거

Question

유명한 "집합 집합"문제를 구현 중입니다. 나는 좋은 해결책이 있다고 생각하지만, 중복 된 것을 포함하고있다. list.unique()가 상황을 취하기를 바랬지 만, 집합에 대해 == 연산자가 정의되지 않았기 때문에 작동하지 않습니다. 세트 세트는 상황을 해결하지 못합니다 (세트 세트를 사용하여).

완성 된 솔루션이 80 %이므로, 내가 가진 알고리즘보다 더 나은 알고리즘이 있다는 것을 알고 있습니다. 그러나 완전히 알고리즘을 다시 작성하지 않고 중복을 제거하는 영리한 방법이 있다면 궁금합니다.

이

MAIN.CPP :

#include "random.hpp" 

using namespace std; 

int main(void) { 

    subsets2(); 

    getchar(); 
    return 0; 
} 

Random.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 

Answer 1

고유은() 모든 consecutive 중복을 제거 여기

내 코드입니다 C의 요소들 선장. 그래서 unique()를 실행하기 전에 sort mylist를 먼저 수행해야합니다.

mylist.sort(); 
    mylist.unique(); 

Answer 2

그냥이 일을 다른 방법으로, 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; 
} 

Answer 3

는 :; '목록에 정의 된

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; 
    }