Implementation of Permutation, Combinations and PowerSet in C++ [duplicate]
Solution 1:
Using STL:
Permutation:
using std::next_permutation
template <typename T>
void Permutation(std::vector<T> v)
{
std::sort(v.begin(), v.end());
do {
std::copy(v.begin(), v.end(), std::ostream_iterator<T>(std::cout, " "));
std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));
}
Combination:
template <typename T>
void Combination(const std::vector<T>& v, std::size_t count)
{
assert(count <= v.size());
std::vector<bool> bitset(v.size() - count, 0);
bitset.resize(v.size(), 1);
do {
for (std::size_t i = 0; i != v.size(); ++i) {
if (bitset[i]) {
std::cout << v[i] << " ";
}
}
std::cout << std::endl;
} while (std::next_permutation(bitset.begin(), bitset.end()));
}
PowerSet:
Note that if the size if less than the number of bit of your integer, you may you that integer instead of vector<bool>
. If the size is known at compile time, prefer std::bitset<N>
over std::vector<bool>
bool increase(std::vector<bool>& bs)
{
for (std::size_t i = 0; i != bs.size(); ++i) {
bs[i] = !bs[i];
if (bs[i] == true) {
return true;
}
}
return false; // overflow
}
template <typename T>
void PowerSet(const std::vector<T>& v)
{
std::vector<bool> bitset(v.size());
do {
for (std::size_t i = 0; i != v.size(); ++i) {
if (bitset[i]) {
std::cout << v[i] << " ";
}
}
std::cout << std::endl;
} while (increase(bitset));
}
Live example