biyección $\{0, 1, \ldots, \binom{|m|}{n}-1\} \longleftrightarrow \binom{m}{n}$

Question

Intento generar números aleatorios que correspondan a estados de un juego. Digamos que hay $|m|$ cuadrados, y $n$ piezas que pueden ocupar las casillas. Entonces puedo tener un total de $\binom{|m|}{n}$ estados, dado que las piezas son indistintas.

Sin embargo, me gustaría transformar el número generado aleatoriamente $\left[0, \binom{|m|}{n}\right)$ en un estado específico, y para ello necesito una biyección $\{0, 1, \ldots, \binom{|m|}{n}-1\}$ $\longleftrightarrow$ $\binom{m}{n}$ .

Un algoritmo que se me ocurre (que puede funcionar) sería en esencia ordenar las piezas, y colocar el $i^\text{th}$ sobre la $i^\text{th}$ cuadrado para empezar. A continuación, itera sobre las piezas, desplazando la pieza situada más a la derecha si la casilla no está ocupada. Cuando una pieza $p_0$ a la izquierda de cualquier otra pieza dada $p_1, \ldots, p_k$ se desplaza a la derecha, luego se desplaza $p_1, \ldots p_k$ a la izquierda en la medida de lo posible de forma que $p_i$ sigue estando en una plaza menor que $p_j$ .

Agradecería que se me orientara en otras direcciones o que se me facilitara cualquier simplificación, etc.

Gracias.

Answer 1

Así que por lo que entiendo, estás tratando de enumerar el conjunto de tamaño- $n$ subconjuntos de un conjunto fijo $\Omega$ de tamaño $m$ para que puedas calcular fácilmente la elección del tamaño $n$ subconjunto únicamente a partir de su índice. Para simplificar, supondré que $\Omega=\{0,\dots,m-1\}$ para que los estados tengan un orden natural.

Con esto, se puede pensar en el conjunto de tamaño- $n$ subconjuntos de $\Omega$ como longitud- $n$ secuencias estrictamente crecientes de números en $\Omega$ y se pueden ordenar lexicográficamente. Esto le da una dirección de la enumeración. Ahora, sólo tenemos que ir hacia atrás.

Si fijamos el primer número de una longitud- $n$ secuencia creciente a ser $k$ entonces los números restantes tienen que encajar en $\{k+1,\dots,m-1\}$ ---un conjunto de tamaño $m-k-1$ lo que significa que hay ${m-k-1\choose n-1}$ longitud- $n$ secuencias crecientes que empiezan por $k$ para cualquier $0\leq k\leq m-1$ . Esta es la clave para que podamos hacer ingeniería inversa del estado a partir del índice. Si nos fijamos en el subproblema de una longitud- $(n-1)$ secuencia creciente de estados en $\{k+1,\dots,m-1\}$ podemos volver a indexar todo desplazando hacia abajo en $k+1$ y resolver el problema recursivo.

En resumen, podemos definir un procedimiento $\def\getState{\operatorname{getState}}\getState(i,n,m,j)$ que imprime el $i$ estado en el orden lexicográfico de tamaño- $n$ subconjuntos del conjunto $\{j,\dots,j+m-1\}$ como sigue:

• si $n=0$ , renunciar

  el único tamaño $0$ subconjunto de un conjunto vacío

• en caso contrario, que $k$ sea maximal con $p := \sum_{j\leq k}{m-j-1\choose n-1}\leq i$ e imprimir $(j+k)$

  esto encuentra el elemento más pequeño del estado

• llamar recursivamente a $\getState(i-p, n-1, m-k-1, j+k+1)$

  el problema restante es encontrar el $(i-p)$ estado en el orden lexicográfico del tamaño- $(n-1)$ subconjuntos del conjunto $\{j+k+1,\dots,j+m-1\}$

Puede utilizar la memoización para acelerar el cálculo de los coeficientes binomiales (utilizando el triángulo de Pascal).

Con el procedimiento anterior, la respuesta a su pregunta original será $\getState(i,n,m,0)$ .

Answer 2

Fuera del $\binom mn$ posible $n$ -subconjuntos de elementos del $m$ cuadrados, $\binom{m-1}{n-1}$ tienen una pieza en la última casilla, y $\binom{m-1}{n}$ no lo hagas.

Así que puedes hacer lo siguiente:

• Si no hay ninguna pieza en la última casilla, utilice este algoritmo recursivamente para la disposición de $n$ piezas en la primera $m-1$ cuadrados. Esto le da un número entre $0$ y $\binom{m-1}{n}-1$ .
• Si hay una pieza en la última casilla, utilice este algoritmo recursivamente para la disposición de $n-1$ piezas en la primera $m-1$ cuadrados. Esto le da un número entre $0$ y $\binom{m-1}{n-1}-1$ . A continuación, añada $\binom{m-1}{n}$ a la misma, obteniendo un número entre $\binom{m-1}{n}$ y $\binom mn - 1$ .

Como caso base para este algoritmo, siempre que $m=n$ o $n=0$ sólo hay una disposición posible, y debes darle el número $0$ .

---

En realidad, si observamos detenidamente el algoritmo recursivo anterior, podemos "desenrollarlo". Obsérvese que sólo tenemos un lugar donde modificamos el número que obtenemos: cuando el $n^{\text{th}}$ pieza está en el $m^{\text{th}}$ cuadrado, añadimos $\binom{m-1}{n}$ al número. (Podemos simplificar esta regla numerando los cuadrados $0, 1, 2, \dots, m-1$ para que el $m-1$ en $\binom{m-1}{n}$ es el número de la última casilla).

Así que si los cuadrados están numerados $0, 1, 2, \dots, m-1$ y las piezas se sitúan en las casillas $0 \le m_1 < m_2 < \dots < m_n \le m-1$ entonces el algoritmo anterior producirá finalmente el valor $$ \binom{m_1}{1} + \binom{m_2}{2} + \dots + \binom{m_n}{n} $$ y podemos imprimirlo directamente. (Pero sin el algoritmo recursivo, sería super poco claro por qué funcionó).