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