PRNG para generar números con n bits establecidos exactamente

Actualmente estoy escribiendo un código para generar datos binarios. Necesito específicamente generar números de 64 bits con un número determinado de bits establecidos; más precisamente, el procedimiento debería tomar algunos y devolver un número pseudoaleatorio de 64 bits con exactamente bits establecidos en , y el resto establecido en 0.$0 < n < 64$$n$$1$

Mi enfoque actual implica algo como esto:

1. Genere un número pseudoaleatorio de 64 bits .$k$
2. Cuente los bits en , almacenando el resultado en .$k$$b$
3. Si , salida ; de lo contrario, vaya a 1.$b = n$$k$

Esto funciona, pero parece poco elegante. ¿Hay algún tipo de algoritmo PRNG que pueda generar números con bits establecidos de manera más elegante que esto?$n$

Lo que necesita es un número aleatorio entre 0 y . El problema entonces es convertir esto en el patrón de bits.${ 64 \choose n } - 1$

Esto se conoce como codificación enumerativa, y es uno de los algoritmos de compresión implementados más antiguos. Probablemente el algoritmo más simple es de Thomas Cover. Se basa en la simple observación de que si tiene una palabra que tiene bits de longitud, donde los bits establecidos son en el orden de bits más significativo, entonces la posición de esta palabra en el orden lexicográfico de todas las palabras con esta propiedad es:$n$$x_k \ldots x_1$

Entonces, por ejemplo, para una palabra de 7 bits:

...y así.

Para obtener el patrón de bits del ordinal, simplemente decodifica cada bit por turno. Algo como esto, en un lenguaje tipo C:

uint64_t decode(uint64_t ones, uint64_t ordinal)
{
    uint64_t bits = 0;
    for (uint64_t bit = 63; ones > 0; --bit)
    {
        uint64_t nCk = choose(bit, ones);
        if (ordinal >= nCk)
        {
            ordinal -= nCk;
            bits |= 1 << bit;
            --ones;
        }
    }
    return bits;
}

Tenga en cuenta que dado que solo necesita coeficientes binomiales de hasta 64, puede calcularlos previamente.

• Cover, T., Enumerative Source Encoding . IEEE Transactions on Information Theory, Vol. IT-19, No 1, enero de 1973.

Muy similar a la respuesta del seudónimo, obtenida por otros medios.

El número total de combinaciones disponibles es accesible por el método de barras y estrellas , por lo que deberá ser . El número total de números de 64 bits de los que intentaría muestrear su número sería obviamente mucho más alto que eso.$c=\binom{64}{n}$

Entonces, lo que necesita es una función que lo pueda llevar desde un número pseudoaleatorio , que va de a , a la combinación de 64 bits correspondiente.$k$$1$$c$

El triángulo de Pascal puede ayudarlo con eso, porque el valor de cada nodo representa exactamente el número de rutas desde ese nodo hasta la raíz del triángulo, y cada ruta se puede hacer para representar una de las cadenas que está buscando, si todos los giros a la izquierda son etiquetado con un , y cada giro a la derecha con un .$1$$0$

Deje que sea ​​el número de bits que quedan por determinar, sea ​​el número de bits que quedan por usar.$x$$y$

Sabemos que , y podemos usarlo para determinar adecuadamente el siguiente bit del número en cada paso:$\binom{x}{y}=\binom{x-1}{y}+\binom{x-1}{y-1}$

$\mathtt{while}\;\;\; x>0$

$\quad \mathtt{if}\;\;\; x>y$

$\qquad \mathtt{if}\;\;\;k>\binom{x-1}{y}: \;\;\;s \leftarrow s\; + \mathtt{"1"}, \;k\leftarrow k-\binom{x-1}{y}, \;y \leftarrow y-1$

$\qquad \mathtt{else}:\; \;s \leftarrow s\; + \mathtt{"0"}$

$\quad \mathtt{else}: \;\;s \leftarrow s\; + \mathtt{"1"}, \;y \leftarrow y-1$

$\quad x \leftarrow x-1$

Otro método bastante elegante es usar la bisección como se describe en esta respuesta de stackoverflow . La idea es mantener dos palabras, una que tenga como máximo un conjunto de k bits y otra que tenga al menos un conjunto de k bits, y usar la aleatoriedad para mover una de estas hacia tener exactamente k bits. Aquí hay un código fuente para ilustrarlo:

word randomKBits(int k) {
    word min = 0;
    word max = word(~word(0)); // all 1s
    int n = 0;
    while (n != k) {
        word x = randomWord();
        x = min | (x & max);
        n = popcount(x);
        if (n > k)
            max = x;
        else
            min = x;
    }
    return min;
}

Hice una comparación de rendimiento de varios métodos y este suele ser el más rápido a menos que se sepa que k es muy pequeño.

Puedes hacer lo siguiente:

1) Generar un número aleatorio, entre y .$k$$1$$64$

2) Establezca th a .$k$$0$$1$

3) Repita los pasos 1 y 2 veces$n$

$A[]$ es una matriz de bits con todos los s$64$$0$

for(i=1 to n)
{
    k=ran(1,65-i) % random number between 1 and 65-i
    for(x=1;x<65;x++)
    {
        if(A[x]==0)k--;
        if(k==0)break;
    }
    A[x]=1;
}