從列表中刪除重複項

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的元素ontainer。因此，在運行unique（）之前，需要先對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; 
    }