Tạo N chọn K Permutations trong C++

Question

Tôi có một hàm nhận n và k để tạo tất cả hoán vị có thể có của n chọn k, và trong khi nó hoạt động cho hầu hết các kết hợp như 5 chọn 3 hoặc 3 chọn 2, nó không cho những người khác như 4 chọn 2. Tôi cần một số trợ giúp tìm và hiểu lỗi. Cảm ơn bạn đã tìm kiếm.

Chức năng:

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

Tôi đang sử dụng các chức năng next_permutation. cplusplus

Khi tôi cố gắng 4 lựa chọn 2, tôi nên nhận được 12 hoán vị, thay vào đó tôi có được điều này:

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   

Trong khi đó, 3 chọn 2 tác phẩm hoàn hảo với 6 hoán vị có thể:

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

Answer 1

Giá trị k đầu tiên được lặp lại lần thứ nk. Đây là một cách dễ dàng, mặc dù không hiệu quả, cách để tránh sự lặp lại:

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

Tuy nhiên, có một cách dễ dàng hơn và hiệu quả hơn để làm điều đó using std :: đảo ngược (từ https://stackoverflow.com/a/2616837/951890)

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

Bí quyết ở đây là nhận ra rằng hoán vị cuối cùng chỉ là đảo ngược của hoán vị đầu tiên, do đó bằng cách đảo ngược các phần tử nk cuối cùng, bạn sẽ tự động chuyển sang hoán vị cuối cùng của các phần tử đó.

Answer 2

Bạn xuất k thành viên đầu tiên của mỗi n! hoán vị. 4! = 24 hoán vị. hai hoán vị đầu tiên là

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

và bạn đã có 1,2 và 1,2

Để có được kết hợp (4,2), bạn có thể, ví dụ, sử dụng vector

{0,0,1,1} 

permute nó, và chỉ số đầu ra của 1 của

Answer 3

Bạn có thể sử dụng như sau:

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

Live example