repeticion - sacar combinaciones en c++

Generando combinaciones en c++

Question

He estado buscando un código fuente para generar una combinación usando c ++. Encontré algunos códigos avanzados para esto, pero eso es bueno solo para un número específico de datos predefinidos. ¿Alguien puede darme algunos consejos, o tal vez, alguna idea para generar combinación? Como ejemplo, supongamos que el conjunto S = {1, 2, 3, ...., n} y elegimos r = 2 fuera de él. La entrada sería r . En este caso, el programa generará matrices de longitud dos, como 5 2 salidas 1 2, 1 3, etc. Tuve dificultades para construir el algoritmo. Me llevó un mes pensar en esto.

Answer 1

El código es similar a generar dígitos binarios. Mantenga una estructura de datos adicional, una matriz permanente [], cuyo valor en el índice i indicará si el elemento de matriz está incluido o no. Y también mantener una variable de conteo. Siempre que cuente == longitud de combinación, imprima elementos basados ​​en permanente [].

#include<stdio.h>

// a[] : given array of chars 
// perm[] : perm[i] is 1 if a[i] is considered, else 0
// index : subscript of perm which is to be 0ed and 1ed
// n     : length of the given input array
// k     : length of the permuted string
void combinate(char a[], int perm[],int index, int n, int k)
{
   static int count = 0;

   if( count == k )
   { 
      for(int i=0; i<n; i++)
        if( perm[i]==1)
          printf("%c",a[i]);
      printf("/n");

    } else if( (n-index)>= (k-count) ){

         perm[index]=1;
         count++;
         combinate(a,perm,index+1,n,k);

         perm[index]=0;
         count--;
         combinate(a,perm,index+1,n,k);

   }
}
int main()
{
   char a[] ={''a'',''b'',''c'',''d''};
   int perm[4] = {0};
   combinate(a,perm,0,4,3);

   return 0;
}

Answer 2

Para el caso especial de (n elegir r) , donde r es una constante fija, podemos escribir r anidados bucles para llegar a la situación. Algunas veces, cuando r no es fijo, podemos tener otro caso especial (n choose nr) , donde r es nuevamente una constante fija. La idea es que cada combinación es la inversa de las combinaciones de (n elegir r). De modo que podemos volver a utilizar r bucles anidados, pero invertir la solución:

// example 1: choose each 2 from given vector and apply ''doSomething''
void doOnCombinationsOfTwo(const std::vector<T> vector) {
   for (int i1 = 0; i1 < vector.size() - 1; i1++) {
      for (int i2 = i1 + 1; i2 < vector.size(); i2++) {
         doSomething( { vector[i1], vector[i2] });
      }
   }
}


// example 2: choose each n-2 from given vector and apply ''doSomethingElse''
void doOnCombinationsOfNMinusTwo(const std::vector<T> vector) {
   std::vector<T> combination(vector.size() - 2); // let''s reuse our combination vector 
   for (int i1 = 0; i1 < vector.size() - 1; i1++) {
      for (int i2 = i1 + 1; i2 < vector.size(); i2++) {
         auto combinationEntry = combination.begin(); // use iterator to fill combination
         for (int i = 0; i < vector.size(); i++) {
            if (i != i1 && i != i2) {
               *combinationEntry++ = i;
            }
         }
         doSomethingElse(combinationVector);
      }
   }
}

Answer 3

Puede implementarlo si observa que para cada nivel r selecciona un número de 1 a n .

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

#include <iostream>
#include <iterator>
#include <vector>
#include <cstdlib>

using namespace std;

struct combinations
{
    typedef vector<int> combination_t;

    // initialize status
   combinations(int N, int R) :
       completed(N < 1 || R > N),
       generated(0),
       N(N), R(R)
   {
       for (int c = 1; c <= R; ++c)
           curr.push_back(c);
   }

   // true while there are more solutions
   bool completed;

   // count how many generated
   int generated;

   // get current and compute next combination
   combination_t next()
   {
       combination_t ret = curr;

       // find what to increment
       completed = true;
       for (int i = R - 1; i >= 0; --i)
           if (curr[i] < N - R + i + 1)
           {
               int j = curr[i] + 1;
               while (i <= R-1)
                   curr[i++] = j++;
               completed = false;
               ++generated;
               break;
           }

       return ret;
   }

private:

   int N, R;
   combination_t curr;
};

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<int>(cout, ","));
        cout << endl;
    }
    return cs.generated;
}

resultado de prueba:

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

Answer 4

Puede usar bucles for si r es pequeño, aquí r = 2, entonces dos para bucles:

unsigned int i, j, max=0;
for(i=1; i<=n; i++){
    for(j=i+1; j<=n; j++){
            int ans = (i & j);
            cout << i << " " << j << endl;     
     }
}

Answer 5

Puede usar la recursión, por lo que para elegir combinaciones de N + 1, elige N combinaciones y luego agrega 1 a ella. El 1 que agregue debe estar siempre después del último de su N, de modo que si su N incluye el último elemento, no hay ninguna combinación N + 1 asociada.

Quizás no sea la solución más eficiente, pero debería funcionar.

El caso base sería elegir 0 o 1. Puedes elegir 0 y obtener un conjunto vacío. Desde un conjunto vacío puede suponer que los iteradores trabajan entre los elementos y no en ellos.

Answer 6

Sugeriría averiguar cómo lo harías en papel e inferir un seudocódigo de eso. Después de eso, solo necesita decidir la forma de codificar y almacenar los datos manipulados.

Por ejemplo:

For each result item in result array // 0, 1, ... r
    For each item possible // 0, 1, 2, ... n
        if current item does not exist in the result array
            place item in result array
            exit the inner for
        end if
    end for
end for

Answer 7

Una forma sencilla de usar std::next_permutation :

#include <iostream>
#include <algorithm>
#include <vector>

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

    std::vector<bool> 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 <iostream>
#include <algorithm>
#include <vector>

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

   std::vector<bool> 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 un "conjunto de selección" ( v ), donde colocamos selectores r , luego creamos todas las permutaciones de estos selectores e imprimimos el miembro del conjunto correspondiente si se selecciona en la permutación actual de v . Espero que esto ayude.

Answer 8

este es un método recursivo, que puede usar en cualquier tipo. puede iterar en una instancia de la clase Combinations (por ejemplo, get () vector con todas las combinaciones, cada combinación es un vector de objetos. Está escrito en C ++ 11.

//combinations.hpp
#include <vector>

template<typename T> class Combinations {
// Combinations(std::vector<T> s, int m) iterate all Combinations without repetition
// from set s of size m s = {0,1,2,3,4,5} all permuations are: {0, 1, 2}, {0, 1,3}, 
// {0, 1, 4}, {0, 1, 5}, {0, 2, 3}, {0, 2, 4}, {0, 2, 5}, {0, 3, 4}, {0, 3, 5},
// {0, 4, 5}, {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}

public:
    Combinations(std::vector<T> s, int m) : M(m), set(s), partial(std::vector<T>(M))
    {
        N = s.size(); // unsigned long can''t be casted to int in initialization

        out = std::vector<std::vector<T>>(comb(N,M), std::vector<T>(M)); // allocate space

        generate(0, N-1, M-1);
    };

    typedef typename std::vector<std::vector<T>>::const_iterator const_iterator;
    typedef typename std::vector<std::vector<T>>::iterator iterator;
    iterator begin() { return out.begin(); }
    iterator end() { return out.end(); }    
    std::vector<std::vector<T>> get() { return out; }

private:
    void generate(int i, int j, int m);
    unsigned long long comb(unsigned long long n, unsigned long long k); // C(n, k) = n! / (n-k)!

    int N;
    int M;
    std::vector<T> set;
    std::vector<T> partial;
    std::vector<std::vector<T>> out;   

    int count (0); 
};

template<typename T> 
void Combinations<T>::generate(int i, int j, int m) {  
    // combination of size m (number of slots) out of set[i..j]
    if (m > 0) { 
        for (int z=i; z<j-m+1; z++) { 
            partial[M-m-1]=set[z]; // add element to permutation
            generate(z+1, j, m-1);
        }
    } else {
        // last position
        for (int z=i; z<j-m+1; z++) { 
            partial[M-m-1] = set[z];
            out[count++] = std::vector<T>(partial); // add to output vector
        }
    }
}

template<typename T> 
unsigned long long
Combinations<T>::comb(unsigned long long n, unsigned long long k) {
    // this is from Knuth vol 3

    if (k > n) {
        return 0;
    }
    unsigned long long r = 1;
    for (unsigned long long d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}

Archivo de prueba:

// test.cpp
// compile with: gcc -O3 -Wall -std=c++11 -lstdc++ -o test test.cpp
#include <iostream>
#include "combinations.hpp"

struct Bla{
    float x, y, z;
};

int main() {

    std::vector<int> s{0,1,2,3,4,5};
    std::vector<Bla> ss{{1, .4, 5.0},{2, .7, 5.0},{3, .1, 2.0},{4, .66, 99.0}};

    Combinations<int> c(s,3);
    // iterate over all combinations
    for (auto x : c) { for (auto ii : x) std::cout << ii << ", "; std::cout << "/n"; }

    // or get a vector back
    std::vector<std::vector<int>> z = c.get();  

    std::cout << "/n/n";

    Combinations<Bla> cc(ss, 2);
    // combinations of arbitrary objects
    for (auto x : cc) { for (auto b : x) std::cout << "(" << b.x << ", " << b.y << ", " << b.z << "), "; std::cout << "/n"; }    

}

salida es:

0, 1, 2, 0, 1, 3, 0, 1, 4, 0, 1, 5, 0, 2, 3, 0, 2, 4, 0, 2, 5, 0, 3, 4, 0, 3, 5, 0, 4, 5, 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,

(1, 0.4, 5), (2, 0.7, 5), (1, 0.4, 5), (3, 0.1, 2), (1, 0.4, 5), (4, 0.66, 99), (2 , 0.7, 5), (3, 0.1, 2), (2, 0.7, 5), (4, 0.66, 99), (3, 0.1, 2), (4, 0.66, 99),

Answer 9

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

// n choose r combination
#include <vector>
#include <iostream>
#include <algorithm>

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<int> myints(r);
    std::vector<int>::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<int>::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

Answer 10

          #include<iostream>
          using namespace std;

          for(int i=1;i<=5;i++)
             for (int j=2;j<=5;j++) 
                if (i!=j)
                  cout<<i<<","<<j<<","<<endl;

           //or instead of cout... you can put them in a matrix n x 2 and use the solution

Answer 11

public static class CombinationGenerator {
    int n;
    int k;
    Integer[] input;
    List<List<Integer>> output;

    public CombinationGenerator(int n, int k) {
        this.n = n;
        this.k = k;
        input = new Integer[n];
        for (int i = 1; i <= n; i++) {
            input[i-1] = i;
        }
    }

    public List<List<Integer>> generate(){
        if(k>n){
            throw new RuntimeErrorException(null, "K should be less than N");
        }
        output = generate(0, k);
        printOutput();
        return output;
    }

    private List<List<Integer>> generate(int cur, int k) {
        List<List<Integer>> output = new ArrayList<List<Integer>>();
        int length = input.length - cur;
        if(length == k){
            List<Integer> result = new ArrayList<Integer>();
            for (int i = cur; i < input.length; i++) {
                result.add(input[i]);
            }
            output.add(result);
        }
        else if( k == 1){
            for (int i = cur; i < input.length; i++) {
                List<Integer> result = new ArrayList<Integer>();
                result.add(input[i]);
                output.add(result);
            }
        }
        else{
            for (int i = cur; i < input.length; i++) {
                List<List<Integer>> partialResult = generate(i+1, k-1);
                for (Iterator<List<Integer>> iterator = partialResult.iterator(); iterator
                        .hasNext();) {
                    List<Integer> list = (List<Integer>) iterator.next();
                    list.add(input[i]);
                }
                output.addAll(partialResult);
            }
        }
        return output;
    }
    private void printOutput(){
        for (Iterator<List<Integer>> iterator = output.iterator(); iterator
                .hasNext();) {
            printList((List<Integer>) iterator.next());
        }
    }
    private void printList(List<Integer> next) {
        for (Iterator<Integer> iterator = next.iterator(); iterator.hasNext();) {
            Integer integer = (Integer) iterator.next();
            System.out.print(integer.intValue());
        }
        System.out.print("/n");
    }


}

Answer 12

void print(int *a, int* s, int ls)
{
    for(int i = 0; i < ls; i++)
    {
        cout << a[s[i]] << " ";
    }
    cout << endl;
}    
void PrintCombinations(int *a, int l, int k, int *s, int ls, int sp)
{
   if(k == 0)
   {
       print(a,s,ls);
       return;
   }
   for(int i = sp; i < l; i++)
   {

      s[k-1] = i;
      PrintCombinations(a,l,k-1,s,ls,i+1);
      s[k-1] = -1;

   }
}

int main()
{
 int e[] = {1,2,3,4,5,6,7,8,9};
 int s[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
 PrintCombinations(e,9,6,s,6,0);
}