Generando combinaciones en c++

Queremos compartir contigo la mejor respuesta que encontramos online. Nosotros esperamos que te sea de ayuda y si puedes compartir algo que nos pueda ayudar a perfeccionar nuestra información hazlo libremente.

Solución:

Una forma sencilla de usar std::next_permutation:

#include 
#include 
#include 

int main() 
    int n, r;
    std::cin >> n;
    std::cin >> r;

    std::vector v(n);
    std::fill(v.end() - r, v.end(), true);

    do 
        for (int i = 0; i < n; ++i) 
            if (v[i]) 
                std::cout << (i + 1) << " ";
            
        
        std::cout << "n";
     while (std::next_permutation(v.begin(), v.end()));
    return 0;

o una ligera variación que genera los resultados en un orden más fácil de seguir:

#include 
#include 
#include 

int main() 
   int n, r;
   std::cin >> n;
   std::cin >> r;

   std::vector v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do 
       for (int i = 0; i < n; ++i) 
           if (v[i]) 
               std::cout << (i + 1) << " ";
           
       
       std::cout << "n";
    while (std::prev_permutation(v.begin(), v.end()));
   return 0;

Un poco de explicación:

Funciona creando una "selección array" (v), donde colocamos r selectores, luego creamos todas las permutaciones de estos selectores e imprimimos el miembro del conjunto correspondiente si está seleccionado en la permutación actual de v. Espero que esto ayude.

Puede implementarlo si observa que para cada nivel r seleccionas un número del 1 al norte.

En C ++, necesitamos mantener 'manualmente' el estado entre llamadas que produce resultados (una combinación): entonces, construimos una clase que en construcción inicializa el estado y tiene un miembro que en cada llamada devuelve la combinación mientras haya soluciones : por ejemplo

#include 
#include 
#include 
#include 

using namespace std;

struct combinations
;

int main(int argc, char **argv)

    int N = argc >= 2 ? atoi(argv[1]) : 5;
    int R = argc >= 3 ? atoi(argv[2]) : 2;
    combinations cs(N, R);
    while (!cs.completed)
    
        combinations::combination_t c = cs.next();
        copy(c.begin(), c.end(), ostream_iterator(cout, ","));
        cout << endl;
    
    return cs.generated;

salida de prueba:

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

mi solución simple y eficiente basada en algoritmos del Prof. Nathan Wodarz:

// n choose r combination
#include 
#include 
#include 

struct c_unique 
  int current;
  c_unique() current=0;
  int operator()() return ++current;
 UniqueNumber;

void myfunction (int i) 
  std::cout << i << ' ';


int main()

    int n=5;
    int r=3;

    std::vector myints(r);
    std::vector::iterator first = myints.begin(), last = myints.end();

    std::generate(first, last, UniqueNumber);

    std::for_each(first, last, myfunction);
    std::cout << std::endl;

    while((*first) != n-r+1)
        std::vector::iterator mt = last;

        while (*(--mt) == n-(last-mt)+1);
        (*mt)++;
        while (++mt != last) *mt = *(mt-1)+1;

        std::for_each(first, last, myfunction);
        std::cout << std::endl;
    

entonces la salida es:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Te mostramos reseñas y calificaciones

---

---

Utiliza Nuestro Buscador