특정 데이터 집합에서 중복을 제거하는 방법은 무엇입니까?

Question

같은 번호 나 동전을 얻기를 원하는 두 명의 어린이가 있다고 가정 해 봅니다 (동전의 명목 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} 

이제 중복없이 컬렉션을 갖고 싶은 I`d :

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

어떻게 최적의 덜 복잡한을 만들기 위해 솔루션을 변경하려면?

Answer 1

당신은 (최적화)를 첫 번째 사이클 후

if (leftSubsetExist) 
    continue; 

를 추가해야

당신이 (다른 동전) 일부 "잘못"순열을 추가 할 수 있을까요?