algorithm - permutations - Creando múltiples números con cierto número de bits establecidos

string permutation

Question

Problema

Necesito crear números de 32 bits (no importa si está firmado o no, nunca se establecerá el bit más alto) y cada número debe tener un número determinado de bits.

Solución ingenua

La solución más fácil es, por supuesto, comenzar con el número de cero. Dentro de un bucle, el número ahora se incrementa en uno, se cuenta el número de Bits, si el conteo tiene el valor deseado, el número se almacena en una lista, si no el bucle simplemente se repite. El ciclo se detiene si se han encontrado suficientes números. Por supuesto, esto funciona bien, pero es terriblemente lento una vez que la cantidad de bits deseados aumenta.

Una mejor solución

El número más simple que tiene (digamos) 5 bits establecidos es el número donde se establecen los primeros 5 bits. Este número se puede crear fácilmente. Dentro de un bucle, se establece el primer bit y el número se desplaza hacia la izquierda en uno. Este ciclo se ejecuta 5 veces y encontré el primer número con 5 bits establecidos. El siguiente par de números también es fácil de crear. Ahora simulamos que el número es de 6 bits de ancho y el más alto no está configurado. Ahora comenzamos a cambiar el primer bit cero a la derecha, así que obtenemos 101111, 110111, 111011, 111101, 111110. Podríamos repetir esto añadiendo otro 0 al frente y repitiendo este proceso. 0111110, 1011110, 1101110, etc. Sin embargo, de esa manera los números crecerán mucho más rápido de lo necesario, ya que al usar este enfoque simple omitimos números como 1010111.

Entonces, ¿hay una mejor manera de crear todas las permutaciones posibles, un enfoque genérico, que se pueda usar, sin importar cuántos bits tenga el próximo número y sin importar cuántos bits de conjunto necesitamos establecer?

Answer 1

Intenta abordar el problema desde el lado opuesto: lo que intentas hacer es equivalente a "encontrar n números en el rango 0-31".

Supongamos que estás tratando de encontrar 4 números. Empiezas con [0,1,2,3] y luego aumentas el último número cada vez (obteniendo [0,1,2,4], [0,1,2,5] ...) hasta que alcances el límite [0,1,2,31]. A continuación, aumente el penúltimo número y establezca el último número en uno más alto: [0,1,3,4]. Vuelve a aumentar el último número: [0,1,3,5], [0,1,3,6] ... etc. Una vez que tocas el final de esto, vuelves a [0,1,4 , 5] - eventualmente llegas a [0,1,30,31] en cuyo punto tienes que retroceder un paso más: [0,2,3,4] y listo. Continúa hasta que finalmente termines con [28,29,30,31].

Dado un conjunto de números, obviamente es fácil convertirlos en números de 32 bits.

Answer 2

Si desea generar combinaciones, consulte este artículo de Wikipedia .

Answer 3

Usted necesita permutaciones fácticas (Google sobre eso) o uno de los algoritmos en Wiki

Answer 4

Puedes usar el truco de hackersdelight.org .

En su libro tiene código para obtener el siguiente número más alto con el mismo número de conjunto de un bit.

Si usa esto como primitivo para aumentar su número, todo lo que tiene que hacer es encontrar un punto de partida. Obtener el primer número con N bits establecido es fácil. Son solo 2 ^ (N-1) -1.

Repetirás todos los números posibles muy rápido de esa manera.

  unsigned next_set_of_n_elements(unsigned x) 
  {
     unsigned smallest, ripple, new_smallest, ones;

     if (x == 0) return 0;
     smallest     = (x & -x);
     ripple       = x + smallest;
     new_smallest = (ripple & -ripple);
     ones         = ((new_smallest/smallest) >> 1) - 1;
     return ripple | ones;
  }

  // test code (shown for two-bit digits)

  void test (void)
  {
    int bits = 2;
    int a = pow(2,bits) - 1;
    int i;

    for (i=0; i<100; i++)
    {
       printf ("next number is %d/n", a);
       a = next_set_of_n_elements(a);
    }
  }