Combinatoria: precomputación de todas las combinaciones sin repetición, necesita una indexación rápida

Question

He hecho una pregunta similar (pero no idéntica) en SO aquí https://stackoverflow.com/questions/5984102 pero las respuestas no son tan útiles porque necesito una indexación muy rápida (y quizás mi pregunta no fue lo suficientemente clara).

Precalculé un montón de valores que tardaron días en ser calculados (con la carga repartida en varios ordenadores). Ahora tengo una enorme tabla de búsqueda a la que tengo que acceder con frecuencia y ese acceso tiene que ser lo más rápido posible.

Básicamente, tengo un problema así: He precalculado los valores de C(38,6) ( es decir . 2 760 681 valores) que ahora se almacenan en una gran tabla de búsqueda. La memoria no es un problema. La precomputación no es un problema. El "orden" no es un problema y puedo reordenarlo como quiera.

Además, C(38,6) es sólo un ejemplo, podría estar necesitando también C(42,7), etc.

Cuando hice la precomputación, básicamente hice un bucle como este (el código real es más complicado para la carga necesaria para ser repartida entre varias máquinas y para el cálculo real no están aquí, pero aquí está la carne de ella):

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            for (int l = k + 1; l < n; l++) {
                for (int m = l + 1; m < n; m++) {
                    for (int o = m + 1; o < n; o++) {
                       ...    
                    }
                }
            }
        }
    }
}

Lo único que importa es tener el tiempo de búsqueda más rápido posible.

Tengo i,j,k,l,m y n todo en [0..37] (o [1..38], no importa) y necesito acceder al elemento precalculado correspondiente en mi enorme matriz de búsqueda lo más rápido posible.

¿Existe una fórmula cerrada para esto que sea rápida de calcular?

Lo que tengo ahora es una búsqueda binaria: mi i será siempre inferior a j , j inferior a k etc. A continuación, he creado un índice arbitrario haciendo:

(i + 1) * (n exp 5) + (j + 1) * (n exp 4) + (k + 1) * (n exp 3) + (l + 1) * (n exp 2) + (m + 1) * n + o

Esto es probablemente exagerado, pero garantiza que no haya colisiones. A continuación, hago una búsqueda binaria en ese índice y encuentro donde se almacena el valor precalculado.

Esto es bastante rápido, pero me preguntaba si hay una forma más rápida de "alcanzar" mi índice precalculado.

Básicamente porque no conozco la combinatoria enumerativa lo suficientemente bien estoy precalculando mi propio índice y usando ese índice para hacer una búsqueda binaria. Esto es rápido pero estoy buscando algo más rápido, como una fórmula cerrada (dudo que algo haciendo "enumeraciones" y i++ o cosas así serían más rápidas que esas pocas multiplicaciones para calcular ese índice + la búsqueda binaria).

Creo que la complejidad de mi método es log(n) pero no estoy seguro.

Answer 1

Si utilizamos la base 1, la observación crítica es la del $\binom{38}{6}=\frac{38!}{32!6!}$ combinaciones, $\binom{37}{5}$ de ellos comenzará con $1$ , $\binom{36}{5}$ de ellos comenzará con 2, y así sucesivamente. Así que dado $(9,12,14,24,33,37)$ Las combinaciones con $9$ en primer lugar comenzará después de $\binom{37}{5}+\binom{36}{5}+\binom{35}{5}+\binom{34}{5}+\binom{33}{5}+\binom{32}{5}+\binom{31}{5}+\binom{30}{5}$ porque así es como muchos comienzan con $1$ a través de $8$ . Entonces, dentro de la $9$ 's, los que tienen $10$ en el número de la segunda posición $\binom{28}{4}$ y los que tienen $11$ en el número de la segunda posición $\binom{27}{4}$ Así que los que empiezan por $(9,12)$ empezar después de eso. Así que esto es después de $\sum_{i=1}^{8}\binom{38-i}{5}+\sum_{i=10}^{11}\binom{38-i}{4}$ . Los que tienen $13$ en la tercera posición número $\binom{25}{3}=\binom{38-13}{3}$ . El patrón debe ser claro. Cuando llegues al final, tendrás el índice en la tabla. También puedes ir al revés, para no tener que precalcular tu tabla -como dices la semana que viene podrías necesitar lo mismo para las combinaciones de $\binom{42}{7}$ . Para encontrar la millonésima combinación, las que tienen un $1$ son $\binom{37}{5}=435897$ y los que tienen un líder $2$ son $\binom{36}{5}=376992$ por lo que queremos que el $187111^{\text{st}}$ uno que comienza con $3$ . Entonces el segundo lugar $4$ son $\binom{34}{4}=46736$ y encontramos que el segundo elemento es $9$ y queremos que el $4625^{\text{th}}$ y así sucesivamente dando (3,9,11,16,27,36)

Answer 2

¡Es bastante absurdo almacenar esto en absoluto! Hay varias formas de anotar las funciones $f:[0,\binom nk]\to\mathcal{P}(\{1,2,\dots,n\}$ que son biyecciones, y computables órdenes de magnitud más rápidas que cualquier búsqueda que implique E/S (seguramente se puede hacer sin ni siquiera obtener un fallo de caché )

Answer 3

El orden aplastado es un buen orden para este tipo de cosas.

Aclaración: Este algoritmo toma un $k$ -subrayado $0\leq a_1<a_2<...<a_k<n$ a un número de índice único de $0$ a ${n \choose k}-1$ .

Dado $k$ enteros, $0\leq a_1<a_2<...<a_k$ el índice de orden aplastado de esta secuencia es ${a_1\choose 1} + {a_2\choose 2} + {a_3 \choose 3} ... + {a_k \choose k}$ . Si su valor máximo para $a_k$ es $n$ se puede precalcular $m \choose i$ para $m\leq n$ y $i\leq k$ para aumentar el rendimiento de este cálculo.

Si $A$ y $B$ son conjuntos de $k$ números naturales, entonces $A$ viene antes que $B$ en el orden aplastado si el mayor número que está en la diferencia simétrica de $A$ y $B$ está en $B$ .

Aparte de la facilidad de calcular el índice de un conjunto, lo otro bueno del orden es que el índice no depende de $n$ .

Véase, por ejemplo: Combinatoria de conjuntos finitos, por Ian Anderson, p. 113 .

Answer 4

Se pueden utilizar los conceptos que se explican aquí: http://msdn.microsoft.com/en-us/library/aa289166%28v=vs.71%29.aspx Pasa del índice lexicográfico a la combinación; creo que esta pregunta es cómo ir en sentido contrario. Ejemplo de implementación en java...

// from http://introcs.cs.princeton.edu/java/96optimization/Binomial.java.html
static long binomial(int n, int k) {
    final long[][] binomial = new long[n + 1][k + 1];

    for (int i = 1; i <= k; i++) binomial[0][i] = 0;
    for (int j = 0; j <= n; j++) binomial[j][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            binomial[i][j] = binomial[i - 1][j - 1] + binomial[i - 1][j];

    return binomial[n][k];
}

static long lexIndex(int n, int... tuple) {
    final int k = tuple.length;

    // map tuple to its combinadic
    final int[] c = new int[k];
    for (int i = 0; i < k; ++i) c[i] = (n - 1) - tuple[i];

    // calculate the lex index of that combinadic
    Arrays.sort(c);
    long result = 0;
    for (int i = 0; i < c.length; i++) result += binomial(c[i], i+1);

    // calculate that index's dual
    return (binomial(n, k) - 1) - result;
}

Si se le da el tamaño del conjunto y la combinación en cuestión, devuelve el índice lexicográfico. Del ejemplo en los comentarios:

lexIndex(38, 9,12,14,24,33,37) = 2321663

También podría hacerlo más rápido calculando la matriz binomial antes de tiempo