¿Como obtener una combinacion mediante su indice?

[Yidu]

Pues me he estancado.

Aunque ya he realizado alguna consulta por la web, no le veo solucion a mi duda. O todavia no tengo los conocimientos para desarrollar el codigo.
Mi duda:

Escogemos 100 numeros del 1 al 100. Y acto seguido pedimos las combinaciones de 5 grupos. Total 75287520 combinaciones. Correcto. Pero,  si por ejemplo, quiero que me de la combinacion con su indice 1000000 me tarda unos 9 segundos a recorrer dichas combinaciones con un ciclo FOR (que tambien probe con un WHILE).

¿Como le puedo pedir a un script que me devuelva de forma inmediata las combinaciones a traves del indice que se le indica? Ya no hablo de arreglos (que se podria hacer para pocos vectores).

La duda me viene por que no se como los programas construyen las combinaciones o el algoritmo que usan.

En el ejemplo que detallo, para encontrar la combinacion que se haya en la posicion o indice 1000000 tarda unos 9 segundos ¿Se puede hacer que de forma inmediata nos la de? Con un FOR, creo, desde luego que no. Ya que debe recorrer todas ellas hasta llegar a la posicion 1000000

Código (python) [Seleccionar] Expandir

import itertools
from datetime import datetime


inicio = datetime.now()
muestra = tuple(range(1, 101))
for indice, x in enumerate(itertools.combinations(muestra, 5),1):
    print(indice, x)
    if indice == 1000000:
        print('La combinacion con indice', indice, 'es', x)
        break
       
final = datetime.now()
tiempo = final - inicio
print(tiempo)

Salida:

Código (python) [Seleccionar] Expandir

...
999994 (1, 9, 18, 21, 29)
999995 (1, 9, 18, 21, 30)
999996 (1, 9, 18, 21, 31)
999997 (1, 9, 18, 21, 32)
999998 (1, 9, 18, 21, 33)
999999 (1, 9, 18, 21, 34)
1000000 (1, 9, 18, 21, 35)
La combinacion con indice 1000000 es (1, 9, 18, 21, 35)
0:00:09.510784


Si pedimos un indice mayor o jugamos con otras combinaciones, nos puede arrojar horas, dias o semanas en devolvernos la combinacion con el indice pedido ¿No?

[DarK_FirefoX]

¿Como le puedo pedir a un script que me devuelva de forma inmediata las combinaciones a traves del indice que se le indica? Ya no hablo de arreglos (que se podria hacer para pocos vectores).

La respuesta corta es NO se puede, ahora de una manera dinámica puedes calcular las combinaciones una vez y almacenarlas (en un array o en otra estructura de datos (preferiblemente que sea más rápido buscar que en un array)) y una vez que quieras una combinación en particular indexas ahí y la devuelves, no obstante, ten en cuenta que calcular todas las combinaciones siempre se va a demorar al menos una vez.

Si pedimos un indice mayor o jugamos con otras combinaciones, nos puede arrojar horas, dias o semanas en devolvernos la combinacion con el indice pedido ¿No?

Si, incluso se te puede acabar el espacio en la pila (si está implementado recursivamente) y darte una excepción de tipo StackOverflow

Nota: También puede que distintas maneras de obtener las combinaciones te arroje una combinación "con el indice" 1000000 y de otra forma de arroje otra combinación diferente "con el indice" 1000000.

Espero haberte aclarado algo.

Salu2s

[Eleкtro]

1. La razón de que el código de arriba demore siglos es por que estás imprimiendo cada valor en el buffer de salida de la consola (stdOut), mientras eso sea así no puedes pretender que la respuesta sea "inmediata". elimina el "print" y resuelto.

2. Puedes disminuir considerablemente el tiempo de "respuesta" omitiendo la escritura en la consola, por ejemplo añadiendo los valores a una variables, y luego, si quieres, imprimir una única vez en la consola:

Código (python) [Seleccionar] Expandir

col    = enumerate(itertools.combinations(muestra, 5),1)
values = ""

for count, value in col:
    values += "\n" + str((count, value))
    if count == 100000:
    print values
        print('La combinacion con indice', count, 'es', value)
        break

2. Con la función enumerate, gracias al iterador estás devolviendo una colección que contiene elementos sin inicializar (Lazy Initialization), es de lo mejor que puedes hacer para acelerar el tiempo de ejecución del algoritmo, y creo que lo único en Python, aunque no domino del todo el lenguaje.

3. Precisamente la ausencia de un índice en la colección enumerable (__getitem__) es lo que permite hacerla iterable, sencillamente cómo ya te han comentado no puedes utilizar un índice, por otro lado, si que puedes implementarlo, ¿pero para que?, dejaría de ser lo que es.

Saludos

[Yidu]

1. La razón de que el código de arriba demore siglos es por que estás imprimiendo cada valor en el buffer de salida de la consola (stdOut), mientras eso sea así no puedes pretender que la respuesta sea "inmediata". elimina el "print" y resuelto.



2. Puedes disminuir considerablemente el tiempo de "respuesta" omitiendo la escritura en la consola, por ejemplo añadiendo los valores a una variables, y luego, si quieres, imprimir una única vez en la consola:

Muchas gracias. Desde luego que mejora considerablemente. De hecho he probado que halle la combinacion 100.000.000 y ha tardado 18 segundos en darla.

El script del punto 2,  lo probare. Ya que aun no sabia que se podia meter la funcion enumerate en una variable.

De todas formas, creo recordar, que probe alguna vez algo parecido a lo que comentas. Osea, que no imprimiera toda la iteracion de las combinaciones por pantalla. Pero claro, como la consola se quedaba en espera no sabia si iba a tardar un minuto en darme el resultado o en un mes   En cambio, al imprimir por pantalla sabes cuantas combinaciones faltan para el testeo. Pero bueno, de momento me conformo con tu idea.

Muchas Gracias!  

[Eleкtro]

El script del punto 2,  lo probare. Ya que aun no sabia que se podia meter la funcion enumerate en una variable.

Hombre, es una función, y cómo toda función siempre puedes asignar su valor de retorno a una variable.

Pero esa variable no tiene relevancia alguna, solo la puse ahí para tener y usar una referencia de la colección enumerable (o dicho de otro modo, para formatear el código, acortándole el nombre a "col" y usando ese nombre).

como la consola se quedaba en espera no sabia si iba a tardar un minuto en darme el resultado o en un mes   En cambio, al imprimir por pantalla sabes cuantas combinaciones faltan para el testeo.

Te entiendo perfectamente, pero imprimir en la consola implica un mayor, mucho mayor tiempo de procesado.

Lo que se suele hacer en estos casos con algoritmos "pesados" es mostrar una barra o texto de progreso indeterminado (ej: "Calculating values, please wait..."), ya que, o prescindes de la información visual en pantalla, o prescindes del rendimiento del algoiritmo en general, ¡tú decides a que darle mayor prioridad!.

Saludos!

[Yidu]

Te entiendo perfectamente, pero imprimir en la consola implica un mayor, mucho mayor tiempo de procesado.

Lo que se suele hacer en estos casos con algoritmos "pesados" es mostrar una barra o texto de progreso indeterminado (ej: "Calculating values, please wait..."), ya que, o prescindes de la información visual en pantalla, o prescindes del rendimiento del algoiritmo en general, ¡tú decides a que darle mayor prioridad!.

Saludos!

Ok. Supongo,  que dependiendo del ordenador, a mi me puede tardar 18 segundos y en otro mas potente, 1 segundo o menos.

RECTIFICACION:

No puedo poner nunca que me de la combianacion 100.000.000. Por el simple hecho que 100 numeros en grupos de 5, da como maximo 75287520 combinaciones.

En todo caso, por ejemplo, ponemos:

Código (python) [Seleccionar] Expandir

if indice == 75000000:
       print('La combinacion con indice', indice, 'es', x)

Y si nos arroja:

Código (python) [Seleccionar] Expandir

La combinacion con indice 75000000 es (66, 77, 86, 90, 100)
0:00:20.209156

[Eleкtro]

Si he entendido bien no te importa demasiado mostrar las tuplas por consola, solo pretendes mostrar un "indicador" que determine el estado de la operación, en ese caso, y según lo que he mencioando antes sobre el rendimiento, quizás esto que escribí te sirva de ayuda:

Código (python) [Seleccionar] Expandir

# -*- coding: UTF-8-*-

import sys, itertools; from datetime import datetime

muestra = tuple(range(1, 101))

print("Init: " + str(datetime.now().time()))

for count, value in enumerate(itertools.combinations(muestra, 5),1):
   
   if (count == 20000000):
       sys.stdout.write( "\rItem with index %s has value of %s\n" % ("{:,}".format(count), str(value)) )
       break

   elif (count%1000000 == 0):
       sys.stdout.write( "\r{:,} indexes checked...".format(count) )
       sys.stdout.flush()

print("End: " + str(datetime.now().time()))



PD: La imagen no está modificada, en realidad tarda 4 segundos, pero al detenerlo intencionadamente para abrir el grabador de video, calculó segundos de más xD.

Saludos

[Yidu]

Si, pero en esos casos el tiempo de calculo es minimo...10 segundos, 20 segundos, incluso horas.

Pero imagina si has de tratar con combinaciones que arrojan cifras como esta:

2.245100430901328e+16

Es decir, 200 numeros en combinaciones de 10 grupos. Ahi, da igual que imprimas por pantalla, que no. Seguramente tardaria años en arrojar algun resultado.

Ya que cuando subimos un poco el numero de grupos,  las combinaciones son intratables.

Por cierto, a mi me tarda unos diez segundos el calculo,  que te tarda cuatro a ti. Eso ya es cosa de ordenadores, supongo.

Tengo una duda con esta linea:

Código (python) [Seleccionar] Expandir

elif (count%1000000 == 0):

¿Que hace realmente? Esta claro que trata de hallar el resto de la operacion ¿Pero el parametro 1000000 es siempre fijo?

[Eleкtro]

Por cierto, a mi me tarda unos diez segundos el calculo,  que te tarda cuatro a ti. Eso ya es cosa de ordenadores, supongo.

Si, a mi me tarda 4 segundos el último código que publiqué (redondeando los milisegundos).

Por supuesto que el tiempo total depende del "PC", de la capacidad/potencia actual de dicho PC para el procesado de las operaciones de computación, siendo esto que acabo de decir una explicación abierta a diferentes interpretaciones (tareas en segundo plano del sistema, CPU, RAM, I/O, fragmentación del disco, etc).

Código (python) [Seleccionar] Expandir

elif (count%1000000 == 0):

¿Que hace realmente?

Determina si el valor "count" es un múltiplo de 1.000.000

¿Por qué 1.000.000 y no 100.000?, para reducir la escritura en el buffer y así incrementar el rendimiento general.

Saludos

[Yidu]

Si, a mi me tarda 4 segundos el último código que publiqué (redondeando los

Determina si el valor "count" es un múltiplo de 1.000.000

¿Por qué 1.000.000 y no 100.000?, para reducir la escritura en el buffer y así incrementar el rendimiento general.

Ah, vale. Aunque no entiendo de todo el proceso. Veo que modificando este valor, el contador va mas deprisa o despacio. Dicho linea la he modificado a:

Código (python) [Seleccionar] Expandir

elif (count%100000000 == 0):

Para un testeo de:

Código (python) [Seleccionar] Expandir

if (count == 1.481076071314056e+16):

Ahora la salida por consola va con una cuenta de 100.000.000. Igual tengo que abortar el proceso, claro. Si todo fuera bien, me tendria que mostrar la ultima combinacion de esas 1.481076071314056e+16.

Me gusta la idea que has mostrado. Ya que de esa forma, no se te inunda la pantalla de tuplas y en cambio aparece como un contador. Lo siguiente seria crear el codigo para que reste las combinaciones que van apareciendo con el total de las mismas. Asi, sabriamos lo que falta para que termine el proceso.

Por cierto, para que este numero:  1.481076071314056e+16 lo podamos dejar en entero con hacer

Código (python) [Seleccionar] Expandir

int(1.481076071314056e+16)
>>> 14810760713140560 es suficiente ¿No?


Saludos!