Algoritmo lexicográfico

Question

Esta pregunta puede ser más adecuada para Stack Overflow, pero tengo debilidad por este sitio, así que pensé en darle una oportunidad:

Estoy intentando hacer un algoritmo (¿podría ser incluso recursivo?) que genere una lista de los posibles resultados de n pruebas de bernoulli. Primero ordenando los resultados por el número de aciertos, luego ordenando esos subconjuntos lexicográficamente . Por ejemplo, con 2 ensayos me gustaría una matriz que se parece a esto: $$ \left(\begin{array}{cc}0&0\\1&0\\0&1\\1&1\end{array}\right) $$ Or, for 3,4,5 trials it would look like: $$ \left(\begin{array}{ccc}0&0&0\\1&0&0\\0&1&0\\0&0&1\\1&1&0\\1&0&1\\0&1&1\\1&1&1\end{array}\right) \ \left(\begin{array}{cccc}0&0&0&0\\1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\1&1&0&0\\1&0&1&0\\1&0&0&1\\0&1&1&0\\0&1&0&1\\0&0&1&1\\1&1&1&0\\1&1&0&1\\1&0&1&1\\0&1&1&1\\1&1&1&1\end{array}\right) \ \left(\begin{array}{ccccc}0&0&0&0&0\\1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\\1&1&0&0&0\\1&0&1&0&0\\1&0&0&1&0\\1&0&0&0&1\\0&1&1&0&0\\0&1&0&1&0\\0&1&0&0&1\\0&0&1&1&0\\0&0&1&0&1\\0&0&0&1&1\\1&1&1&0&0\\1&1&0&1&0\\1&1&0&0&1\\1&0&1&1&0\\1&0&1&0&1\\1&0&0&1&1\\0&1&1&1&0\\0&1&1&0&1\\0&1&0&1&1\\0&0&1&1&1\\1&1&1&1&0\\1&1&1&0&1\\1&1&0&1&1\\1&0&1&1&1\\0&1&1&1&1\\1&1&1&1&1\end{array}\right)$$ Esta disposición es importante debido a la disposición de otras entradas para el script R que estoy escribiendo.

EDIT: Acabo de darme cuenta de algo interesante: la matriz es simétrica en cierto modo... si doblas después de la fila central, un 0 corresponde a un 1 (y viceversa) en la posición opuesta al pliegue.

¿Alguna idea? Ahora mismo estoy pensando en hacer salidas lexicográficas para cada conjunto de resultados que compartan un número de aciertos y luego enmendarlas? Pero incluso entonces estoy teniendo dificultades para producir las permutaciones lexicográficas.

¿Alguna idea? ¿O debería mover esto a Stack Overflow?

Answer 1

Una recursión podría ser así para $w=0,\ldots,n-1$ , pasar por todo el peso $w$ entradas para dimensión $n-1$ y los muestra precedidos de un "0"; recorre todos los pesos $w$ entradas para dimensión $n-1$ de nuevo y mostrarlos precedidos de un "1".

Answer 2

Enumerar los resultados de $k$ éxitos en $n$ en orden lexicográfico, puede proceder recursivamente:

1) (si $k \ge 1$ ) enumera los resultados de $k-1$ éxitos en $n-1$ juicios, y añadir $1$ a cada uno.

2) (si $k \le n-1$ ) enumera los resultados de $k$ éxitos en $n-1$ juicios, y añadir $0$ a cada uno.

Answer 3

Para $n$ bits, tendrá $1$ palabra de todos los bits cero, $n$ palabras con una sola $1$ poco, $n(n-1)/2$ con dos $1$ bits, y generalmente ${n \choose k}$ con $k$ $1$ bits. Para el lote con $k$ $1$ bits, el primero ${n-1 \choose k-1}$ comenzará con $1$ y el resto ${n-1 \choose k}$ comenzará con $0$ . Se obtiene así un algoritmo recursivo:
Principal
Para k=0 a n
Para i=0 a ${n \choose k}-1$
Imprimir f(n,k,i)

Función f(n,k,i)# devuelve el $i^{\text{th}}$ de ${n \choose k}$ cadenas de $n$ bits con $k$ $1$ bits en orden lexicográfico
Si $i \lt {n-1 \choose k-1}$ devolver $1+$ f(n-1,k-1,i)
Si no, devuelva $0+$ f(n-1,k,i- ${n-1 \choose k-1}$ )

Answer 4

Se trata de un caso muy especial en el que se pide un ordenamiento lexicográfico de n vectores de enteros cuya suma no puede superar un número k dado. Existe una bonita fórmula cerrada para ello, por lo que realmente no se necesita recursividad para calcular el número de rango de cada vector (por supuesto, la recursividad se utilizará para demostrarlo). La especialidad viene de restringir las entradas en las coordenadas del vector a un máximo de 1. No sé si necesitas la tabla completa o sólo los números de rango. En este último caso, mi fórmula puede ser de gran ayuda. Si sigues interesado, házmelo saber.