¿Es posible obtener el elemento k-ésimo de la combinación m-carácter-longitud en O (1)?

Question

¿Conoces alguna forma de obtener el elemento k-ésimo de la combinación m-elemento en O (1)? La solución esperada debería funcionar para cualquier tamaño de datos de entrada y cualquier valor m.

Me explico este problema por ejemplo (código Python):

>>> import itertools 
>>> data = ['a', 'b', 'c', 'd'] 
>>> k = 2 
>>> m = 3 
>>> result = [''.join(el) for el in itertools.combinations(data, m)] 
>>> print result 
['abc', 'abd', 'acd', 'bcd'] 
>>> print result[k-1] 
abd 

Para una de datos dado el k-ésimo (2-nd en este ejemplo) elemento de combinación m-elemento es abd. ¿Es posible ese valor (abd) sin crear toda la lista combinatoria?

He preguntado porque tengo datos de ~ 1,000,000 de caracteres y es imposible crear una lista combinatoria de longitud de m completo para obtener el elemento k-ésimo.

La solución puede ser un pseudo código, o un enlace en la página que describe este problema (desafortunadamente, no encontré ninguno).

Gracias!

Answer 1

No necesariamente O (1), pero el siguiente debe ser muy rápido:

Tome el algoritmo combinaciones originales:

def combinations(elems, m): 
    #The k-th element depends on what order you use for 
    #the combinations. Assuming it looks something like this... 
    if m == 0: 
     return [[]] 
    else: 
     combs = [] 
     for e in elems: 
      combs += combinations(remove(e,elems), m-1) 

Para n elementos iniciales y m longitud de la combinación, hemos n!/(n-m)!m! combinaciones totales . Podemos utilizar este hecho para saltar directamente a nuestra combinación deseada:

def kth_comb(elems, m, k): 
    #High level pseudo code 
    #Untested and probably full of errors 
    if m == 0: 
     return [] 
    else: 
     combs_per_set = ncombs(len(elems) - 1, m-1) 
     i = k/combs_per_set 
     k = k % combs_per_set 
     x = elems[i] 
     return x + kth_comb(remove(x,elems), m-1, k) 

Answer 2

primero calcular r = !n/(!m*!(n-m)) con n la cantidad de elementos

entonces piso (r/k) es el índice del primer elemento en el resultado ,

retirarla (cambiar todo lo siguiente a la izquierda)

do M--, n-- y k = r% k

y repita hasta que m es 0 (pista cuando k es 0 sólo copiar los siguientes caracteres al resultado)

Answer 3

http://en.wikipedia.org/wiki/Permutation#Numbering_permutations

Básicamente, expresar el índice en el sistema de número factorial, y el uso de sus dígitos como una selección de la secuencia original (sin reemplazo).

Answer 4

He escrito una clase para manejar las funciones comunes para trabajar con el coeficiente binomial, que es el tipo de problema que parece ser su problema. 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. 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. Creo que también es más rápido que otras técnicas publicadas.

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 Java, Python o C++.