Calcular rango de una combinación?

Question

Quiero calcular previamente algunos valores para cada combinación en un conjunto de combinaciones. Por ejemplo, al elegir 3 números del 0 al 12, voy a computo algún valor para cada uno:

>>> for n in choose(range(13), 3): 
    print n, foo(n) 

(0, 1, 2) 78 
(0, 1, 3) 4 
(0, 1, 4) 64 
(0, 1, 5) 33 
(0, 1, 6) 20 
(0, 1, 7) 64 
(0, 1, 8) 13 
(0, 1, 9) 24 
(0, 1, 10) 85 
(0, 1, 11) 13 
etc... 

quiero para almacenar estos valores en una matriz de modo que, dada la combinación, puedo calcular y obtener su el valor. Por ejemplo:

>>> a = [78, 4, 64, 33] 
>>> a[magic((0,1,2))] 
78 

¿Cuál sería magic?

Inicialmente pensé simplemente almacenarlo como una matriz tridimensional de tamaño 13 x 13 x 13, por lo que puedo indizarlo fácilmente de esa manera. Si bien esto está bien para 13 elegir 3, esto tendría demasiada sobrecarga para algo como 13 elegir 7.

No quiero usar un dict porque eventualmente este código estará en C, y una matriz sería mucho más eficiente de todos modos.

ACTUALIZACIÓN: También tengo un problema similar, pero el uso de combinaciones con repeticiones, por lo que cualquier respuesta sobre cómo obtener el rango de los sería muy apreciada =).

ACTUALIZACIÓN: Para dejar en claro, estoy tratando de ahorrar espacio. Cada una de estas combinaciones en realidad se indexa en algo que ocupa mucho espacio, digamos 2 kilobytes. Si tuviera que usar una matriz de 13x13x13, sería 4 megabytes, de los cuales solo necesito 572 kilobytes usando (13 elijo 3) puntos.

Answer 1

Aquí hay una respuesta conceptual y un código basado en cómo funciona el orden lex. (Así que supongo que mi respuesta es como la de "idiota", excepto que creo que tiene muy pocos detalles y sus enlaces tienen demasiados). Escribí una función unchoose(n,S) para usted que funciona suponiendo que S es un subconjunto de lista ordenada de range(n). La idea: O S contiene 0 o no. Si lo hace, elimine 0 y calcule el índice para el subconjunto restante. Si no lo hace, entonces se produce después de las binomial(n-1,k-1) subconjuntos que contienen 0.

def binomial(n,k): 
    if n < 0 or k < 0 or k > n: return 0 
    b = 1 
    for i in xrange(k): b = b*(n-i)/(i+1) 
    return b 

def unchoose(n,S): 
    k = len(S) 
    if k == 0 or k == n: return 0 
    j = S[0] 
    if k == 1: return j 
    S = [x-1 for x in S] 
    if not j: return unchoose(n-1,S[1:]) 
    return binomial(n-1,k-1)+unchoose(n-1,S) 

def choose(X,k): 
    n = len(X) 
    if k < 0 or k > n: return [] 
    if not k: return [[]] 
    if k == n: return [X] 
    return [X[:1] + S for S in choose(X[1:],k-1)] + choose(X[1:],k) 

(n,k) = (13,3) 
for S in choose(range(n),k): print unchoose(n,S),S 

Ahora, también es cierto que se puede almacenar en caché o valores hash de ambas funciones, binomial y unchoose. Y lo bueno de esto es que puede comprometerse entre precomputar todo y precomputar nada. Por ejemplo, puede precalcular solo para len(S) <= 3.

También puede optimizar la opción de no selección para que agregue los coeficientes binomiales con un bucle si es S[0] > 0, en lugar de disminuir y usar la recursividad de cola.

Answer 2

Puede intentar usar el índice lexicográfico de la combinación. Tal vez esta página ayude: http://saliu.com/bbs/messages/348.html

Esta página de MSDN tiene más detalles: Generating the mth Lexicographical Element of a Mathematical Combination.

a ser un poco más específico:

Cuando se trata como una tupla, puede ordenar las combinaciones lexicográfico.

Así que (0,1,2) < (0,1,3) < (0,1,4), etc.

Supongamos que tenía el número 0 a n-1 y k escogido de aquellos .

Ahora, si el primer elemento es cero, usted sabe que es uno de los primeros n-1 elija k-1.

Si el primer elemento es 1, entonces es uno entre los siguientes n-2 elija k-1.

De esta forma puede calcular de forma recursiva la posición exacta de la combinación dada en el orden lexicográfico y usarla para asignarla a su número.

Esto funciona al revés también y la página de MSDN explica cómo hacerlo.

Answer 3

Use una tabla hash para almacenar los resultados. Una función hash decente podría ser algo como:

h(x) = (x1*p^(k - 1) + x2*p^(k - 2) + ... + xk*p^0) % pp

Dónde x1 ... xk son los números de la combinación (por ejemplo (0, 1, 2) tiene x1 = 0, x2 = 1, x3 = 2) y p y pp son números primos.

Así que almacenaría Hash[h(0, 1, 2)] = 78 y luego lo recuperaría de la misma manera.

Nota: la tabla hash es simplemente una matriz de tamaño pp, no es un dict.

Answer 4

Sugeriría una tabla hash especializada. El hash para una combinación debe ser exclusivo o de los valores hash para los valores. Los valores hash para los valores son básicamente patrones de bits aleatorios.

Puede codificar la tabla para hacer frente a las colisiones, pero debería ser bastante fácil derivar un esquema de hash perfecto mínimo, uno donde no hay dos combinaciones de tres elementos que den el mismo valor hash, y donde el tamaño y tabla de hash tamaño se mantienen al mínimo.

Esto es básicamente Zobrist hashing - piense en un "movimiento" como agregar o quitar un elemento de la combinación.

EDITAR

La razón para usar una tabla hash es que el rendimiento de la búsqueda O (n) donde n es el número de elementos en la combinación (suponiendo que no hay colisiones). El cálculo de índices lexicográficos en las combinaciones es significativamente más lento, IIRC.

El inconveniente es obviamente el trabajo inicial realizado para generar la tabla.

Answer 5

Por ahora, he llegado a un compromiso: Tengo una matriz 13x13x13 que acaba asigna al índice de la combinación, tomando 13x13x13x2 bytes = 4 kilobytes (usando enteros cortos), más el tamaño normal (13 elija 3) * 2 kilobytes = 572 kilobytes, para un total de 576 kilobytes. ¡Mucho mejor que 4 megabytes, y también más rápido que un cálculo de rango!

Lo hice en parte porque parecía que la respuesta de Moron no funcionaba. También esto es más extensible. Tengo un caso en el que necesito combinaciones con repeticiones, y aún no he encontrado una forma de calcular el rango de esas.

Answer 6

Lo que quiere se llama combinadics.Aquí está mi aplicación de este concepto, en Python:

def nthresh(k, idx): 
    """Finds the largest value m such that C(m, k) <= idx.""" 
    mk = k 
    while ncombs(mk, k) <= idx: 
    mk += 1 
    return mk - 1 


def idx_to_set(k, idx): 
    ret = [] 
    for i in range(k, 0, -1): 
    element = nthresh(i, idx) 
    ret.append(element) 
    idx -= ncombs(element, i) 
    return ret 


def set_to_idx(input): 
    ret = 0 
    for k, ck in enumerate(sorted(input)): 
    ret += ncombs(ck, k + 1) 
    return ret 

Answer 7

He escrito una clase para manejar las funciones comunes para trabajar con el coeficiente binomial, que es el tipo de problema que su problema cae bajo. Realiza las siguientes tareas:

1. Muestra todos los índices K en un formato agradable para cualquier N elije K a un archivo. Los índices K pueden sustituirse por cadenas o letras más descriptivas. Este método hace que resolver este tipo de problema sea bastante trivial.

2. Convierte los índices K al índice adecuado de una entrada en la tabla de coeficientes binomiales ordenados. Esta técnica es mucho más rápida que las técnicas publicadas más antiguas que se basan en la iteración y no utiliza mucha memoria. Hace esto usando una propiedad matemática inherente al Triángulo de Pascal. Mi periódico habla de esto. Creo que soy el primero en descubrir y publicar esta técnica, pero podría estar equivocado.

3. Convierte el índice en una tabla de coeficientes binomiales ordenados a los índices K correspondientes.

4. Utiliza el método Mark Dominus para calcular el coeficiente binomial, que es mucho menos probable que se desborde y funciona con números mayores.

5. La clase está escrita en .NET C# y proporciona una forma de gestionar los objetos relacionados con el problema (si corresponde) mediante el uso de una lista genérica. El constructor de esta clase toma un valor bool llamado InitTable que cuando sea verdadero creará una lista genérica para contener los objetos que se administrarán. Si este valor es falso, no creará la tabla. No es necesario crear la tabla para realizar los 4 métodos anteriores. Se proporcionan métodos de acceso para acceder a la tabla.

6. Hay una clase de prueba asociada que muestra cómo usar la clase y sus métodos. Ha sido ampliamente probado con 2 casos y no hay errores conocidos.

Para leer sobre esta clase y descargar el código, consulte Tablizing The Binomial Coeffieicent.

No debería ser difícil convertir esta clase a C++.