samedi 2 décembre 2017

How to remove duplicates in particular set of data?

Lets suppose we have two childs who want to get same number or coins (coin nominals 1,2,6,12). Childs dont care about the value. Example container of permutations which I want to share between two childs:

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

Now I`d like to have collections without duplicates:

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

That permutations are wrong:

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

because

child A     child B
1 2         1 2 

is permutation of

child A     child B
2 1         2 1 

which we already have. These collections: 1 2 2 1 and 2 1 1 2 are permutations, as well.

My solution is here, works correctly for that particular input but if you add more coins with different nominals, it doesn`t!

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

How to change the solution to make optimal and less complex?

Aucun commentaire:

Enregistrer un commentaire