mercredi 20 juin 2018

Count of combinations with repititions

I have a very inefficient way of counting the combinations of N/2 items from an array of size N. What I do is sort the array to begin with and then loop through the the permutations of the array, creating multisets with half the elements and insert that into a set. Finally I get the count of the set.

Here's the code in C++:

long GetCombinations(std::vector<double> nums)
{
    long combinations = 0;

    std::sort(nums.begin(), nums.end());

    std::set<std::multiset<double>> super_set;

    do
    {
        std::multiset<double> multi_set;

        for (unsigned int i = 0; i < nums.size() / 2; ++i)
        {
            multi_set.insert(nums[i]);
        }

        auto el = (super_set.insert(multi_set));

        if (el.second)
        {
            ++combinations;
        }
    } while (std::next_permutation(nums.begin(), nums.end()));

    return combinations;
}

The code works but it is very inefficient. For the given array [0.5, 0.5, 1, 1] there are 3 combinations of size 2:
0.5, 0.5
1, 1
1, 0.5

I guess my code could be replaced by a different algorithm, but I don't know how.

Can someone help?

Aucun commentaire:

Enregistrer un commentaire