如何刪除特定數據集中的重複項？

假設我們有兩個孩子想要相同的數字或硬幣（硬幣名義1,2,6,12）。孩子們不在乎價值。我想要兩個孩子的之間共享排列的例子容器：如何刪除特定數據集中的重複項？

{1, 1, 1, 1, 1, 1}, 
{1, 1, 2, 2}, 
{1, 2, 1, 2}, 
{1, 2, 2, 1}, 
{2, 1, 1, 2}, 
{2, 1, 2, 1}, 
{2, 2, 1, 1}

現在我想要一份有集合沒有重複：

child A  child B 
2 2   1 1 
2 1   2 1 
1 1   2 2 
1 1 1  1 1 1

排列是錯誤的：

1 2 1 2 
1 2 2 1 
2 1 1 2

因爲

child A  child B 
1 2   1 2

是

child A  child B 
2 1   2 1

排列，我們已經有了。這些集合：1 2 2 1和2 1 1 2也是排列組合。

我的解決方案是在這裏，爲特定的輸入正確工作，但如果你添加更多的硬幣與不同的名義，它不！

#include <iostream> 
#include <vector> 
#include <unordered_set> 

using namespace std; 

int main() 
{ 
    vector<vector<int>> permutations = 
    { 
     {1, 1, 1, 1, 1, 1}, 
     {1, 1, 2, 2}, 
     {1, 2, 1, 2}, 
     {1, 2, 2, 1}, 
     {2, 1, 1, 2}, 
     {2, 1, 2, 1}, 
     {2, 2, 1, 1} 
    }; 
    vector<pair<unordered_multiset<int>, unordered_multiset<int>>> childSubsets; 

    for(const auto &currentPermutation : permutations) 
    { 
      size_t currentPermutationSize = currentPermutation.size(); 
      size_t currentPermutationHalfSize = currentPermutationSize/2; 
      //left 
      unordered_multiset<int> leftSet; 

      for(int i=0;i<currentPermutationHalfSize;++i) 
       leftSet.insert(currentPermutation[i]); 

      bool leftSubsetExist = false; 
      for(const auto &subset : childSubsets) 
      { 
       if(subset.first == leftSet) 
       { 
        leftSubsetExist = true; 
        break; 
       } 
      } 
      //right 
      unordered_multiset<int> rightSet; 

      for(int i = currentPermutationHalfSize; i < currentPermutationSize; ++i) 
       rightSet.insert(currentPermutation[i]); 

      bool rightSubsetExist = false; 
      for(const auto &subset : childSubsets) 
      { 
       if(subset.second == rightSet) 
       { 
        rightSubsetExist = true; 
        break; 
       } 
      } 
      //summarize 
      if(!leftSubsetExist || !rightSubsetExist) childSubsets.push_back({leftSet, rightSet}); 
    } 
    cout << childSubsets.size() << endl; 
}

如何更改解決方案以實現最優化和更簡單？

來源

2017-12-02 John Friday

*如何刪除特定數據集中的重複項？* - 不要將重複項存儲在首位。使用'std :: unordered_set'。 – PaulMcKenzie

std :: unordered_set不允許包含重複項。在該算法中可能有例如2,2套在一套。 –

你應該第一個週期（如優化）之後添加

if (leftSubsetExist) 
    continue;

你可以添加一些「錯誤」排列（與另一硬幣）？

來源

2017-12-04 13:42:02

如何刪除特定數據集中的重複項？

回答

相關問題