Pseudo generador de números aleatorios con densidad fija de 1s

Question

Estoy buscando la forma de generar números pseudoaleatorios [posiblemente de baja "aleatoriedad"] o secuencias de bits pseudoaleatorias con un peso de Hamming fijo [una densidad fija de 1s]. He encontrado alguna sugerencia sobre el uso de un simple generador de congruencia lineal con una semilla que tiene el peso Hamming que necesito, pero no se dio ninguna razón por qué esto es correcto [por qué el peso de Hamming es invariante bajo la transformación de congruencia lineal]

podría alguien ¿razonar ese punto o darme otra manera?

Gracias ...

Answer 1

editar: Pitón hace que sea fácil para mezclar cosas

from random import shuffle 

def gen(ham, bits=32): 
    # generate a list with the correct number of 1's 
    x = [1]*ham+[0]*(bits-ham) 
    shuffle(x) 
    # convert back to a number 
    return int(''.join(map(str,x)),2) 

>> print('\n'.join(bin(gen(5,15)) for x in range(10))) 
0b101100100001000 
0b100110010010 
0b100110110000000 
0b10010101100 
0b11101100000 
0b100100001000110 
0b10000010101001 
0b110000011100000 
0b100011100010 
0b100000011100010 

---

Aquí es una forma posible (básicamente, generar permutaciones aleatorias de una cadena de base:

1. generan un número factodico aleatorio N hasta su profundidad de bits.
2. convertir el factoradic a Permutación índice de lista

3. convertir su lista de permutación al bit-array (ilustrado en la pseudo-pitón):

   [x < peso para x en perm_list]

Answer 2

No he oído hablar sobre el uso de un LCG para generar un peso fijo de hamming (no me metí tanto en los códigos de Hamming en la escuela, así que tampoco estoy demasiado sorprendido :).

En cualquier caso, es bastante sencillo generar un montón de bits con un peso fijo fijo. Aquí hay un poco de código de pitón que devolverá un número de n -bit con un peso particular. Esto también debería traducirse fácilmente a otros idiomas (aparte del hecho de que los enteros de pitón son arbitrariamente grandes).

from random import randrange 

def get_ham_and_bits(weight, nbits=32): 
    "Get n-bits with a fixed hamming weight" 
    if weight > nbits: 
     return 1 < nbits 

    result = 0 
    for i in xrange(weight): 
     bit = 1 << randrange(nbits) 

     # only flip bits that aren't already flipped. delete the loop to 
     # make this return a random weight instead of a fixed weight 
     while bit & result != 0: 
      bit = 1 << randrange(nbits) 

     # An XOR might be a better idea here, especially if you remove the loop. 
     result |= bit 
    return result 

Answer 3

uso de un generador de pseudo número al azar (PRNG), incluso una simple con una semilla bajo peso definitivamente no es un una buena solución. El PRNG no mantiene constante el peso Hamming de la semilla, y la idea de un PRNG es eliminar la información de la semilla.

Si quiere tener exacly bits sets en 1 de n, su pregunta es una variante de thesetwo preguntas. Si k es mucho más pequeño que n, la solución de mezcla es O (n). Creo que la siguiente solución es O (k).

Se basa en this answer, en pitón

from random import sample 

def konesoutofn(k, n): 
    output=0 
    for d in sample(xrange(n), k):output+=(1<<d) 
    return output 

x=konesoutofn(4,32) 
print(bin(x)) 

Si quiere tener que tener aproximadamente k bits sets a uno, con k/n siendo la probabilidad de cada bit a ser uno entonces usted tiene que mira las distribuciones de Bernouilli y Geometric.