Elige al azar entre los números que arroja una cantidad específica de 1 binario

Question

Quiero elegir aleatoriamente entre cualquiera de los números decimales que - cuando se convierte en números binarios - va a producir la misma cantidad de 1 binario dentro de un total de 16 bits. No importa que los bits que son 1 como puedo escoger al azar de todas las variaciones.

Por ejemplo, si yo quería que el resultado sea un 1, y 15 0 dentro de los 16 bits, yo tendría que elegir aleatoriamente a cualquiera de los números: 1, 2, 4, 8, 16 et c.

Por lo tanto, que iba a necesitar algo de ayuda para encontrar una función que me permita:

1. primera entrada de una suma determinada de 1: n
2. luego de determinar que los valores decimales que produce cualquier variación de n 1 dentro de los 16 bits.
3. y por último, elegir al azar de cualquiera de estos números.

El aporte se agradece!

Answer 1

El algoritmo a utilizar depende de (a) las capacidades de su plataforma de software; (b) ¿cuántos de esos sorteos que usted necesita; (c) que tan grande es el número de dígitos $n$; y (d) de cómo es de grande el número de posibles resultados de $\binom{n}{k}$ (donde $k$ es el número de unidades).

La mayoría de los estadísticos del trabajo se hace con 32 o 64 entero con signo y/o doble precisión de punto flotante de IEEE números, así que voy a suponer que de (una). Aquí es un conjunto de soluciones que se ilustra con el trabajo R código. Para ser más específicos, todos ellos dibujar de manera uniforme, de forma independiente, y de forma aleatoria de entre el conjunto de $\mathcal{B}(n,k)$ de enteros que, cuando se representan en binario, tienen hasta el $n$ dígitos de los cuales exactamente $k$ son queridos.

1. Usted necesita un único entero aleatorio. Tomar una muestra $i_1, i_2, \ldots, i_k$ sin sustitución, a partir del conjunto de lugares $0,1,\ldots, n-1$ y regresar $2^{i_1} + 2^{i_2} + \cdots + 2^{i_k}.$

   rchoose <- function(n, k) sum(2^sample(0:(n-1), k))
   

   Este algoritmo ha $O(n)$ tiempo y los requisitos de almacenamiento.

2. Se necesita un gran número de $N$ de enteros aleatorios donde $n$ $k$ son pequeñas. "Pequeño" significa (1) el sistema representa con exactitud todos los números enteros a través de $2^{n}-1$ y (2) usted tiene suficiente velocidad y memoria RAM para calcular y almacenar todos los elementos de a $\mathcal{B}(n,k).$

   La solución es generar una matriz que representa todos los elementos de a $\mathcal{B}(n,k)$ y, a continuación, (rápidamente) sorteo al azar a partir de esta matriz:

   rchoose.many <- function(N, n, k) {
     b <- colSums(2^combn(0:(n-1), k))
     sample(b, N, replace=TRUE)
   }
   

   Este algoritmo requiere de $O(n \binom{n}{k})$ tiempo para inicializar $O(N)$ adicional de tiempo para ejecutar. Sus requisitos de almacenamiento se $O(n \binom{n}{k})$ (pero podría ser reducido a $O(\binom{n}{k})$ por la acumulación de los valores en un bucle durante la inicialización).

3. Se necesita un gran número de enteros aleatorios donde $n$ $k$ no son pequeños. Usted todavía está limitado por la necesidad de representar a $n$dígitos binarios enteros en su sistema. De lo mejor que puede hacer es loop $N$ veces el único empate de la solución (1):

   rchoose.many.large <- function(N, n, k) {
     replicate(N, rchoose(n, k))
   }
   

   Esto se lleva a $O(Nn)$ tiempo y $O(n)$ almacenamiento.

La comparación de la asintótico de requisitos proporciona un criterio para la selección de la solución adecuada en cualquier situación.

Ejemplos

Estos tiempos (en un modesto puesto de trabajo) proporcionar alguna indicación de las posibilidades.

system.time(x <- rchoose.many(1, 33, 7))   # 8 sec.
system.time(x <- rchoose.many(1e5, 33, 7)) # 8 sec.
system.time(x <- rchoose.many(1, 33, 16))  # (Not run: would take about 35 min.)

system.time(x <- rchoose.many.large(1e5, 33, 7))  # 0.8 sec.
system.time(x <- rchoose.many.large(1e5, 33, 16)) # 0.9 sec.

He aquí un histograma de una largish de la muestra (de un millón atrae a) muestra la distribución de $n=10,k=4.$ Los recipientes tienen que ser más amplio que el de $1$, de lo contrario la cuenta va a ser $0$ o cerca de una constante (ya que la distribución es uniforme en $\mathcal{B}(10,4)$). Elegí un ancho de $4:$

library(ggplot2)
ggplot(data.frame(x=rchoose.many(1e6, 10, 4)), aes(x)) + geom_histogram(binwidth=4)