Generation N selects K Permutations in C ++

Question

I have a function that gets n and k to create all possible permutations of n, selects k, and although it works for most combinations like 5, select 3 or 3, choose 2, this is not for others like 4 choose 2 I need help finding and understanding the error. Thanks for watching.

Function:

void PermGenerator(int n, int k) { int d[] = {1,2,3,4,5,6,7,8,9}; sort (d, d+n); cout << "These are the Possible Permutations: " << endl; do { for (int i = 0; i < k; i++) { cout << d[i] << " "; if (i == k-1) cout << endl; } } while (next_permutation(d, d+n)); } 

I am using the next_permutation function. cplusplus

When I try 4 to select 2, I should get 12 permutations, instead I get the following:

 1 2 1 2 1 3 1 3 1 4 1 4 2 1 2 1 2 3 2 3 2 4 2 4 3 1 3 1 3 2 3 2 3 4 3 4 4 1 4 1 4 2 4 2 4 3 4 3 

While 3 chooses 2, it works fine with 6 possible permutations:

 1 2 1 3 2 1 2 3 3 1 3 2 

Answer 1

The first values ​​of k are repeated nk factorial times. Here's a simple, albeit ineffective, way to avoid repetition:

 int Factorial(int n) { int result = 1; while (n>1) { result *= n--; } return result; } void PermGenerator(int n, int k) { std::vector<int> d(n); std::iota(d.begin(),d.end(),1); cout << "These are the Possible Permutations: " << endl; int repeat = Factorial(nk); do { for (int i = 0; i < k; i++) { cout << d[i] << " "; } cout << endl; for (int i=1; i!=repeat; ++i) { next_permutation(d.begin(),d.end()); } } while (next_permutation(d.begin(),d.end())); } 

However, there is an even simpler and more efficient way to do this using std :: reverse (from fooobar.com/questions/178234 / ... )

 void PermGenerator(int n, int k) { std::vector<int> d(n); std::iota(d.begin(),d.end(),1); cout << "These are the Possible Permutations: " << endl; do { for (int i = 0; i < k; i++) { cout << d[i] << " "; } cout << endl; std::reverse(d.begin()+k,d.end()); } while (next_permutation(d.begin(),d.end())); } 

The trick here is to understand that the last permutation is only the flip side of the first permutation, therefore, turning the last elements of nk, you automatically go to the last permutation of these elements.

Answer 2

You can use the following:

 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())); } 

Living example

Answer 3

You print the first k members of every n! Permutations. 4! = 24 permutations. The first two permutations:

 1,2,3,4 1,2,4,3 

and you have 1,2 and 1,2

To get combinations (4,2), you can, for example, use the vector

  {0,0,1,1} 

rearrange it and display indices 1