indexar todas las combinaciones sin hacer la lista

Question

Cuál es la forma más eficiente de encontrar la combinación i's de todas las combinaciones sin repetir y sin crear primero todas las combinaciones hasta i. K es fijo (número de elementos en cada combinación) y N es fijo (número de elementos a combinar). El orden no importa, aunque hay que tener en cuenta que si se encuentra i en el siguiente orden...

---

1

2

3

4

5

6

7

8

1,2,3,4

1,2,3,5

1,2,3,6

1,2,4,5

1,2,4,6

1,2,5,6

1,3,4,5

1,3,4,6

9

10

11

12

13

14

15

1,3,5,6

1,4,5,6

2,3,4,5

2,3,4,6

2,3,5,6

2,4,5,6

3,4,5,6

Answer 1

Obsérvese que el primer número sólo cambia después de que el resto haya realizado una serie completa de combinaciones dentro del subconjunto en el que deberían estar, es decir, tenemos $$ |\{1xyz\mid 2\leq x<y<z\leq 6\} $$ haciendo un total de $\binom53=10$ combinaciones que comienzan con $1$ ya que los tres números $x,y$ y $z$ se eligen entre los cinco valores posibles $2,3,4,5$ y $6$ . Del mismo modo, tenemos $$ |\{2xyz\mid 3\leq x<y<z\leq 6\} $$ dándonos $\binom43=4$ combinaciones que comienzan con $2$ . Basándonos en este principio, podemos hacer una lista de valores para los que cambia el primer dígito: $$ \begin{array}{|c|c|} \hline \text{form}&\text{last }i&\text{formula for last }i\\ \hline 1xyz&10&\binom53=10\\ 2xyz&14&10+\binom43=10+4\\ 3xyz&15&14+\binom33=14+1\\ \hline \end{array} $$

---

Este principio puede repetirse hasta el siguiente nivel: Supongamos que encontramos el $58$ -ésima combinación $C=[x,y,z]$ de $k=3$ números elegidos entre $1,2,...,10=n$ . Entonces vemos que $$ \begin{array}{|c|c|} \hline x&y&z&\text{last }i&\text{formula for last }i\\ \hline 1&y&z&36&\binom92=36\\ 2&y&z&64&36+\binom82=36+28\\ \hline &3&z&43&36+\binom71=36+7\\ &4&z&49&43+\binom61=43+6\\ &5&z&54&49+\binom51=49+5\\ &6&z&58&54+\binom41=54+4\\ \hline &&7&55&54+\binom30=54+1\\ &&8&56&55+\binom20=55+1\\ &&9&57&56+\binom10=56+1\\ &&10&58&57+\binom00=57+1\\ \hline \end{array} $$ Siguiendo la lógica de la tabla anterior tenemos $C=[2,6,10]$ y de hecho: $$ 58=1+\underbrace{\binom 92}_{\text{1st digit}}+\underbrace{\binom71+\binom61+\binom51}_{\text{2nd digit}}+\underbrace{\binom30+\binom20+\binom10}_{\text{3rd digit}} $$ donde cada dígito puede derivarse ahora del número de términos $1,3,3$ arriba de la siguiente manera: $$ \begin{align} x&=1+1&=2\\ y&=x+1+3&=6\\ z&=y+1+3&=10 \end{align} $$

---

Aquí hay un código Python donde se implementa esto:

def C(n,k): #computes nCk, the number of combinations n choose k
    result = 1
    for i in range(n):
        result*=(i+1)
    for i in range(k):
        result/=(i+1)
    for i in range(n-k):
        result/=(i+1)
    return result

def cgen(i,n,k):
    """
    returns the i-th combination of k numbers chosen from 1,2,...,n
    """
    c = []
    r = i+0
    j = 0
    for s in range(1,k+1):
        cs = j+1
        while r-C(n-cs,k-s)>0:
            r -= C(n-cs,k-s)
            cs += 1
        c.append(cs)
        j = cs
    return c

Tenga en cuenta que este método no calcula nunca las combinaciones anteriores, pero sí tiene que calcular y sumar las cifras correspondientes a la cantidad de combinaciones anteriores. Pero es realmente rápido. Por ejemplo, le pedí que calculara cgen(173103094564,100,10) que es el $173103094564$ -a combinación de $k=10$ números elegidos entre $1,2,...,100=n$ y respondió inmediatamente:

[1, 3, 5, 11, 19, 25, 38, 66, 80, 82]

que nunca habría adivinado, ni construido a través de $173103094564$ ¡iteraciones!

---

Sólo para mostrar la fuerza de la misma, acabo de hacer

cgen(68814103099439929837637702193841,1000,15)->
[7, 198, 280, 324, 448, 456, 517, 607, 668, 695, 697, 875, 879, 924, 954]

que en realidad tardó unos 3 segundos en calcularse. No deberíamos quejarnos si comparamos esto con tener que construir primero el $68814103099439929837637702193840$ combinaciones anteriores - ¡eso sería inviable!

Answer 2

Sólo un resumen rápido de lo que se describe en Sistema numérico combinatorio en Wikipedia (y en otros lugares). El orden es lexicográficamente creciente con combinaciones individuales escritas en disminuyendo (así que en tu ejemplo esto hace que todas las combinaciones con un $6$ vienen después de los que no tienen $6$ (a diferencia del orden que has enumerado).

Para que la descripción sea más fácil, dos cosas deben ser $0$ -Basado en: las combinaciones deben ser del conjunto $\{0,1,\ldots,n-1\}$ (por lo que hay que restar $1$ de cada elemento para llegar a esta forma), y la lista de combinaciones comienza en el índice $~0$ . Sin embargo, los elementos de una combinación se indexarán por sí mismos $c_1,\ldots,c_k$ en orden creciente. Entonces el $k$ -combinación $\{c_1,\ldots,c_k\}$ viene en la posición $\binom{c_1}1+\binom{c_2}2+\cdots+\binom{c_k}k$ que, por supuesto, es fácil de calcular. El punto esencial es que estos números son diferentes para diferentes $k$ -combinaciones, ver bajo el enlace para más detalles.