For example, (n = 3, k = 2)
, I have set {1, 2, 3}
and I need my algorithm to find:
{1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}
.
I was able to make an algorithm with next_permutation
, but it works very slow for n = 10, k = 4
(which is what I need).
Here's my code:
#include <iostream>
#include <algorithm>
#define pb push_back
using namespace std;
int main() {
vector <int> s = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int k = 4; // (n = 10, k = 4)
map <string, int> m; // To check if we already have that variation
vector <string> v; // Variations
do {
string str = "";
for (int i = 0; i < k; i++) str += to_string(s[i]);
if (m[str] == 0) {
m[str] = 1;
v.pb(str);
}
} while (next_permutation(s.begin(), s.end()));
return 0;
}
How can I make an algorithm that does this faster?
Combinations are selections of objects, with or without repetition, order does not matter. The number of k-element combinations of n objects, without repetition is Cn,k = (n k ) = n! k!( n − k)! .
How many combinations with 16 numbers without repetition are possible? There's one (1) possible combination without repetitions and 300,540,195 combinations with repetitions of arranging a group of sixteen numbers (i.e., the 1-16 number list).
Thus you have made 5 × 4 × 3 × 2 1 = 120 choices and there are 120 possible 5 digit numbers made from 1, 2, 3, 4 and 5 if you don't allow any digit to be repeated.
This code generates arrangements of k items from n in lexicographic order, packed into integer for simplicity (so 153 corresponds to (1,5,3))
void GenArrangement(int n, int k, int idx, int used, int arran) {
if (idx == k) {
std::cout << arran << std::endl;
return;
}
for (int i = 0; i < n; i++)
if (0 == (used & (1 << i)))
GenArrangement(n, k, idx + 1, used | (1 << i), arran * 10 + (i + 1));
}
int main()
{
GenArrangement(5, 3, 0, 0, 0);
}
123 124 125 132 134 135 142 143 145 152 153 154 213 214 215 231 234 235 241 243 245 251 253 254 312 314 315 321 324 325 341 342 345 351 352 354 412 413 415 421 423 425 431 432 435 451 452 453 512 513 514 521 523 524 531 532 534 541 542 543
You can iterate over every subset with a bitmask.
for(unsigned int i = 0; i < (1<<10);i++)
When you do not need portable code you could use
__builtin_popcount(int)
To get the number of 1s in the binary representation at least in gcc with an x86 processor.
for(unsigned int i = 0; i < (1<<10);i++) {
if(__builtin_popcount(i) == 4) { //Check if this subset contains exactly 4 elements
std::string s;
for(int j = 0; j < 10; j++) {
if(i&(1<<j)) { //Check if the bit on the j`th is a one
s.push_back(to_string(j));
}
}
v.push_back(s);
}
}
The slowness is due to generating all n! permutations, even when only a fraction of them is required. Your complexity is around O(n! * k log n), where O(k log n) is an upper bound on the complexity to query the std::map
with all of the permutations.
The answer by MBo is limited to 9 values (1..9). Even if it is extended to printing longer values, they are still limited by number of bits (usually 31 for int, and 64 bit if uint64_t is available).
Here it is:
void print_permutations_impl(std::ostream & out, std::vector<int> & values,
unsigned k, std::vector<int> & permutation_stack)
{
if (k == permutation_stack.size())
{
const char* prefix = "";
for (auto elem: permutation_stack) {
out << prefix << elem;
prefix = ", ";
}
out << '\n';
return;
}
auto end_valid = values.size() - permutation_stack.size();
permutation_stack.push_back(0);
for (unsigned i=0 ; i < end_valid; ++i) {
permutation_stack.back() = values[i];
std::swap(values[i], values[end_valid - 1]);
print_permutations_impl(out, values, k, permutation_stack);
std::swap(values[i], values[end_valid - 1]);
}
permutation_stack.pop_back();
}
void print_permutations(std::ostream & out, const std::vector<int> & values, int k)
{
std::vector<int> unique = values;
std::sort(unique.begin(), unique.end());
unique.erase(std::unique(unique.begin(), unique.end()),
unique.end());
std::vector<int> current_permutation;
print_permutations_impl(out, unique, k, current_permutation);
}
It works in sub-second speed for N=100 and K=2.
Using std::next_permutation
and bitset
(currently std::prev_permutation
to have lexicographic order and std::vector<bool>
instead of std::bitset
to allow dynamic size):
template <typename T>
void Combination(const std::vector<T>& v, std::size_t count)
{
assert(count <= v.size());
std::vector<bool> bitset(count, 1);
bitset.resize(v.size(), 0);
do {
for (std::size_t i = 0; i != v.size(); ++i) {
if (bitset[i]) {
std::cout << v[i] << " ";
}
}
std::cout << std::endl;
} while (std::prev_permutation(bitset.begin(), bitset.end()));
}
Demo
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With