desplazamiento en modo bit para generar todas las permutaciones posibles en C

Question

Duplicar posibles:
Creating multiple numbers with certain number of bits set

Estoy intentando escribir un código que pondrá a cada posible combinación de números en una matriz por desplazando los bits a través de.

Por ejemplo, yo quería encontrar todas las combinaciones posibles de 3 bits (donde el máximo de una dígito puede tener es 6) la matriz debe contener:

000111 
001011 
001101 
001110 
010011 
010101 
010110 
011001 
011010 
011100 
100011

Y así sucesivamente ...

Según lo que he interpretado, cuando el último bit de posición es 1, cambiamos el número por 1 (x >> 1) y agregamos un 1 al inicio. Sin embargo, no estoy seguro de cómo codificar el resto. Estoy usando C para escribir esto.

Además, hasta donde puedo decir que esta es una secuencia de colex, sin embargo, soy todo oídos si hay otra secuencia que me dará el mismo resultado final (matriz con todas las combinaciones posibles de k bits con una restricción de N).

Answer 1

Puede resolver esto generando las secuencias recursivamente.

Definamos una función recursiva f(int index, int bits, int number) que se llevará en la corriente index de la broca y el número de bits izquierda a otro, y el number generado hasta el momento. Luego, tiene la opción de establecer el bit actual en 1 o en 0, y recurrir desde allí.

En general, la complejidad de tiempo debe ser O (número de secuencias), o O (N elegir B), donde N es el número de dígitos y B es el número de bits puestos a 1.

La función es algo como esto:

void f(int index, int bits, int number) { 
    if (index == 0) { 
     if (bits == 0) { // all required bits have been used 
      emit_answer(number); // chuck number into an array, print it, whatever. 
     } 
     return; 
    } 

    if (index-1 >= bits) { // If we can afford to put a 0 here 
     f(index-1, bits, number); 
    } 

    if (bits > 0) { // If we have any 1s left to place 
     f(index-1, bits-1, number | (1 << (index-1))); 
    } 
} 

// to call: 
f(6, 3, 0); 

Para N,B = 6,3 la salida coincide con la suya, y está ordenada. Enlace al ejemplo de trabajo: http://codepad.org/qgd689ZM

Answer 2

Probablemente exista una forma más eficiente, ¿pero podría simplemente recorrer los números y rechazar los números que no cuentan un número de bits de 3? Ver this answer para el conteo de bits.

Answer 3

No hay necesidad de ninguna recursión de lujo. Algunas matemáticas simples serán suficientes (se requiere una división por un valor que siempre será una potencia de dos).

 
    Function nextBits(ByVal prevVal As Integer) 
     Dim lsOne As Integer = ((prevVal - 1) And Not prevVal) + 1 
     Dim nextZero As Integer = (prevVal + lsOne) And Not prevVal 
     Dim lowBits As Integer = ((nextZero \ lsOne \ 2) - 1) 
     Return prevVal + lsOne + lowBits 
    End Function 

Agradable y fácil.