We are given n disjoint, finite sets.
We would like to count the amount of all possible subsets, while having the following restriction: we are only allowed to include a max of one element each out of every of our n disjoint sets.
My initial thought was to count all possible subsets of size {0, 1, ..., n} and sum them up.
Code vector<int64_t> subsets(n + 1);
subsets[0] = 1; // empty set
// runs in O(2 ^ n * n)
for (int mask = 1; mask < (1 << n); mask += 1) {
int subsetSize = __builtin_popcount(mask);
int64_t count = 1;
for (int j = 0; j < n; j++) {
if (mask & (1 << j))
count *= v[j]; // v[j] == size of j'th disjoint set
}
subsets[subsetSize] += count;
}
int64_t ans = 0;
for (int sz = 0; sz <= n; sz++) {
ans += subsets[sz];
}
cout << ans << "\n";
There is probably a much more elegant and efficient solution out there.
Feel free to share your ideas!
Full text and comments »