La generazione N sceglie Permutazioni K in C++

Question

Ho una funzione che riceve n ek per creare tutte le possibili permutazioni di n scegliere k, e mentre funziona per la maggior parte delle combinazioni come 5 scegli 3 o 3 scegli 2, non lo fa per altri come 4 scegli 2. Ho bisogno di aiuto per trovare e capire il bug. Grazie per aver guardato.

La funzione:

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

sto usando la funzione next_permutation. cplusplus

Quando provo 4 Scegliere 2, dovrei ottenere 12 permutazioni, invece ottengo questo:

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   

considerando che, 3 scegliere 2 funziona perfettamente con 6 possibili permutazioni:

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

Answer 1

I primi valori k sono ripetuti in tempi fattoriali nk. Ecco un semplice, anche se inefficiente, modo per evitare la ripetizione:

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

Tuttavia, c'è un modo ancora più semplice e più efficace per farlo utilizzando std :: inverso (da 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())); 
} 

Il trucco qui è rendersi conto che l'ultima permutazione è solo l'opposto della prima permutazione, quindi invertendo gli ultimi elementi nk, si salta automaticamente all'ultima permutazione di quegli elementi.

Answer 2

Emetti i primi k membri di ogni n! permutazioni. 4! = 24 permutazioni. I primi due sono permutazioni

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

e vi hanno preso 1,2 e 1,2

Per ottenere combinazioni (4,2), si potrebbe, ad esempio, utilizzare vettore

{0,0,1,1} 

permutarlo e generare indici di 1

Answer 3

è possibile utilizzare il seguente:

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