我正在执行着名的“集合子集”问题。我想我有一个很好的工作解决方案,但它包含重复。我希望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
还有一个'模板<类BinaryPredicate>无效独特(BinaryPredicate binary_pred);'对列表定义。当然,唯一性只会删除列表中的“下一个”元素。 – Yuushi
删除重复项目听起来像是一个bandaid以解决更严重的问题。为什么您的代码首先创建重复项?这个问题的一个好的算法应该避免完全重复创建。 –