Algoritmo para generar todas las matrices posibles de unos y ceros de una longitud determinada

Question

¿Cómo puedo generar todas las posibles combinaciones de bits en una matriz de bits de longitud n? Si empiezo con todos los ceros en mi matriz, entonces hay n posibilidades de colocar el primer bit y para estas n posibilidades hay n-1 posibilidades de colocar el segundo bit ... unidad, todos los n bits se establecen en uno. Pero hasta ahora no logré programarlo.

También muchas personas señalaron que puedo hacer esto contando de 0 a (2^n) -1 e imprimiendo el número en binario. Esta sería una manera fácil de resolver el problema, sin embargo, en este caso, simplemente dejo que la máquina cuente en lugar de decirle dónde colocarlos. Hago esto para aprender, así que me gustaría saber cómo programar el enfoque de ubicación de las personas.

Answer 1

¿Cómo contaría manualmente en papel? Verificaría el último dígito. Si es 0, lo configura en 1. Si ya es 1, lo vuelve a establecer en 0 y continúa con el siguiente dígito. Entonces es un proceso recursivo.

El siguiente programa genera todas las combinaciones posibles mediante la mutación de una secuencia:

#include <iostream> 

template <typename Iter> 
bool next(Iter begin, Iter end) 
{ 
    if (begin == end)  // changed all digits 
    {      // so we are back to zero 
     return false;  // that was the last number 
    } 
    --end; 
    if ((*end & 1) == 0) // even number is treated as zero 
    { 
     ++*end;   // increase to one 
     return true;  // still more numbers to come 
    } 
    else     // odd number is treated as one 
    { 
     --*end;   // decrease to zero 
     return next(begin, end); // RECURSE! 
    } 
} 

int main() 
{ 
    char test[] = "0000"; 
    do 
    { 
     std::cout << test << std::endl; 
    } while (next(test + 0, test + 4)); 
} 

El programa funciona con cualquier secuencia de cualquier tipo. Si necesita todas las combinaciones posibles al mismo tiempo, simplemente colóquelas en una colección en lugar de imprimirlas. Por supuesto, necesita un tipo de elemento diferente, porque no puede poner matrices C en un vector. Vamos a usar un vector de cadenas:

#include <string> 
#include <vector> 

int main() 
{ 
    std::vector<std::string> combinations; 
    std::string test = "0000"; 
    do 
    { 
     combinations.push_back(test); 
    } while (next(test.begin(), test.end())); 
    // now the vector contains all pssible combinations 
} 

Si no te gusta la recursividad, aquí es una solución iterativa equivalente:

template <typename Iter> 
bool next(Iter begin, Iter end) 
{ 
    while (begin != end)  // we're not done yet 
    { 
     --end; 
     if ((*end & 1) == 0) // even number is treated as zero 
     { 
      ++*end;   // increase to one 
      return true;  // still more numbers to come 
     } 
     else     // odd number is treated as one 
     { 
      --*end;   // decrease to zero and loop 
     } 
    } 
    return false;    // that was the last number 
} 

Answer 2

FredOverflow es correcto en general.

Sin embargo, para 1s & 0s será mejor que simplemente incrementar un número entero de 0:

int need_digits = 10 
unsigned int i=0 
while (! i>>need_digits){ 
    # convert to binary form: shift & check, make an array, or cast to string, anything. 
    } 

... supongo que no tendrá más de 32 bits o usted tendría que múltiples cadenas enteros ... y se adhieren a la respuesta anterior :)

Answer 3

Tales problemas se resuelven trivialmente de manera funcional. Para encontrar las soluciones de longitud n, primero encontrará las soluciones de longitud n-1 y luego agregará '0' y '1' a esas soluciones, duplicando el espacio de la solución.

Aquí es un simple programa recursivo Haskell:

comb 0 = [[]] 

comb n = 
    let rest = comb (n-1) 
    in map ('0':) rest 
    ++ map ('1':) rest 

Y aquí es una prueba de funcionamiento:

> comb 3 
["000","001","010","011","100","101","110","111"] 

Answer 4

Un "verdadero" enfoque recursivo en C++:

#include <iostream> 
#include <string> 

void print_digits(int n, std::string const& prefix = "") { 
    if (!n) { 
     std::cout << prefix << std::endl; 
     return; 
    } 
    print_digits(n-1, prefix + '0'); 
    print_digits(n-1, prefix + '1'); 
} 

int main(int, char**) { 
    print_digits(4); 
} 

Answer 5

óptima la solución está aquí:

http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

Answer 6

Esta es mi respuesta. La ventaja es que todas las combinaciones se guardan en una matriz de dos dimensiones, pero la desventaja es que solo se puede usar para aguijonear hasta 17 dígitos.

#include <iostream> 

using namespace std; 

int main() 
    { 
    long long n,i1=0,i2=0, i=1, j, k=2, z=1; 
    cin >> n; 
    while (i<n){ 
     k = 2*k; 
     i++; 
    } 
    bool a[k][n], t = false; 
    j = n-1; 
    i1=0; 
    i2 = 0; 
    z = 1; 
    while (j>=0){ 
     if(j!=n-1){ 
     z=z*2; 
     } 
     i2++; 
     t = false; 
     i = 0; 
    while (i<k){ 
     i1 = 0; 
     while (i1<z){ 
      if(t==false){ 
      a[i][j]=false; 
      } 
      else { 
       a[i][j]= true; 
      } 
      i1++; 
      i++; 
     } 
     if(t==false){ 
      t = true; 
     }else { 
      t = false; 
     } 
    } 
    j--; 
    } 
    i = 0; 
    j = 0; 
    while (i<k){ 
     j = 0; 
     while (j<n){ 
      cout << a[i][j]; 
      j++; 
     } 
     cout << endl; 
     i++; 
    } 
    return 0; 
}