SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: Riddick en Jueves 4 de Diciembre de 2008, 23:52

Título: Millones de Combinaciones
Publicado por: Riddick en Jueves 4 de Diciembre de 2008, 23:52
Buenas noches a todos y felicidades por el foro. Os cuento:

Estoy intentando programar algo en c++ referente a la primitiva/bonoloto, ya sabeis casi 14 millones de combinaciones posibles (13983816 exactamente) y el problema que tengo es que a la hora de programar todas las combinaciones lo hago con 6 bucles for:

for (i=1;i<45;i++)
for (j=i+1;j<46;j++)
for (k=j+1k<47;k++)
for (l=k+1;l<48;l++)
for (m=l+1;m<49;m++)
for (n=m+1;n<50;n++)

y me tarda en torno a unos 10 minutos en recorrer todas las combinaciones posibles. Porque tarde 10 minutos no hay problema pero es que ahora me encuentro con una parte en la que las tengo que recorrer unas 1000 veces, osea 1000*13983816 (una pasada!!!!!)
He intentado hacer otro codigo, con 6 while...... e incluso con un solo while y varios if tambien lo he hecho pero nada de nada, sigue teniendo que recorrer todos los registros y tarda mucho o mejor dicho tarda lo mismo.

La pregunta es. ¿No habra algun algoritmo o libreria o ambas cosas o lo que sea; que pueda generar esas casi 14 millones de combinaciones en segundos?

Posible sé que es, porque no teneis nada mas que descargaros cualquier programa de primitivas/bonolotos que hay gratuitos y vereis como en unos 4 segundos, y tirando por lo alto, se generan todas las combinaciones. Pero ojo! solo en memoria, lo de la escritura en disco tarda algo mas, pero no 10 minutos.

Gracias por vuestra atencion. Cualquier idea sera bienvenida.
Saludos.

Resumiendo: Generar 14 millones de combinaciones en unos segundos.

PD: se me olvidaba deciros, por si sirve de algo, que he probado con varios compiladores, tanto con borland como devp, tambien con CodeBlocks, incluso en visual basic, en visual c++ y en c#. Y 3 tantos de lo mismo.
Título: Re: Millones de Combinaciones
Publicado por: m0skit0 en Viernes 5 de Diciembre de 2008, 09:43
No creo que dependa del compilador, sino de la máquina. Si puedes acceder a una máquina con 2 o más procesadores (y un SO que sepa usarlas, claro) entonces si notarás un cambio. Son muchas combinaciones y es normal que tarde tanto.

P.D: ¿Has probado en Linux?

EDIT: Perdón, no había leído bien el post... No me hagas caso.
Título: Re: Millones de Combinaciones
Publicado por: Eternal Idol en Viernes 5 de Diciembre de 2008, 09:56
¿Los otros programas funcionan bien en la misma maquina y S.O.? Entonces no hace falta cambiar lo uno ni probar lo otro (FUD).

Tal vez esos programas lanzan varios hilos para procesar en paralelo los numeros mientras que el tuyo lo hace todo en el hilo principal ... no lo se, habria que ver de cerca alguno de esos programas y tu codigo.
Título: Re: Millones de Combinaciones
Publicado por: Riddick en Viernes 5 de Diciembre de 2008, 10:44
En primer lugar muchas gracias a los dos.

En linux no lo he hecho rular y los programas los he ejecutado en mi misma maquina, AMD 5600 Dual Core 2Gb de Ram DDRII 800Mhz y con W XP, y lo dicho, no llegan ni a 4 segundos, seguro que vosotros mismos los podeis probrar, son gratuitos. No se si se pueden decir los nombres de los programas en el foro, pero vamos que hay muchos, gratuitos y rapidos, que es de lo que se trata.

En la opcion de ejecutar varios hilos paralelamente habia pensado, pero creia que no se podia hacer, sabeis como? No tengo ni idea.

Respecto al codigo, al mio, imaginaros lo mas simple, los 6 bucles que puse antes y al final un cout o printf o lo que mas useis. Y respecto a los demas programas ojala tenga el codigo del motor de calculo. Pero que va.
Título: Re: Millones de Combinaciones
Publicado por: Eternal Idol en Viernes 5 de Diciembre de 2008, 11:55
Cita de: "Riddick"
En linux no lo he hecho rular y los programas los he ejecutado en mi misma maquina, AMD 5600 Dual Core 2Gb de Ram DDRII 800Mhz y con W XP, y lo dicho, no llegan ni a 4 segundos, seguro que vosotros mismos los podeis probrar, son gratuitos. No se si se pueden decir los nombres de los programas en el foro, pero vamos que hay muchos, gratuitos y rapidos, que es de lo que se trata.

Bien, entonces es un problema particular de tu ejecutable y no esta relacionado ni con el hardware ni con el S.O. que usas. Claro que podes mencionar esos programas  :comp:

Cita de: "Riddick"
En la opcion de ejecutar varios hilos paralelamente habia pensado, pero creia que no se podia hacer, sabeis como? No tengo ni idea.

Todavia no se EXACTAMENTE que queres hacer pero estas combinaciones no tienen ningun tipo de azar, son siempres las mismas si les pasamos los mismos parametros (las restricciones del total de numeros y su rango). ¿Verdad? Entonces puede ser que estos programas tengan de alguna manera precalculados los resultados (o parte de ellos) estaticamente ...

Cita de: "Riddick"
Respecto al codigo, al mio, imaginaros lo mas simple, los 6 bucles que puse antes y al final un cout o printf o lo que mas useis.

¿No tienen que ser combinaciones de 6 numeros entre 1 y 49? ¿Seguro que conseguis todas las combinaciones correctas con esos bucles? Me imagino que cuando un numero sale ya no se puede repetir ...

Cita de: "Riddick"
Y respecto a los demas programas ojala tenga el codigo del motor de calculo. Pero que va.

Siempre se pueden desensamblar ...

Este codigo no es muy flexible pero en teoria tiene todas las combinaciones que vos queres y tarda menos de un segundo en calcularlas (si las mostras en consola tarda un siglo):
Código: Text
  1.  
  2. #include <windows.h>
  3. #include <stdio.h>
  4.  
  5. void main()
  6. {
  7.     unsigned int comb = 0;
  8.  
  9.     OutputDebugString("startrn");
  10.     char *data = (char*)malloc(13983816 * 6);
  11.     printf("%prn", data);
  12.  
  13.     char *m_data = data;
  14.  
  15.     for (int i=1;i<45;i++)
  16.     {
  17.         for (int j=i+1;j<46;j++)
  18.         {
  19.             for (int k=j+1;k<47;k++)
  20.             {   
  21.                 for (int l=k+1;l<48;l++)
  22.                 {
  23.                     for (int m=l+1;m<49;m++)
  24.                     {
  25.                         for (int n=m+1;n<50;n++)
  26.                         {
  27.                             m_data[0] = i;
  28.                             m_data[1] = j;
  29.                             m_data[2] = k;
  30.                             m_data[3] = l;
  31.                             m_data[4] = m;
  32.                             m_data[5] = n;
  33.                             m_data += 6;
  34.                             comb++;
  35.                         }
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.     }
  41.    
  42.     OutputDebugString("endrn");
  43.     printf("%urn", comb);
  44.     free(data);
  45. }
  46.  
  47.  
Título: Re: Millones de Combinaciones
Publicado por: Riddick en Viernes 5 de Diciembre de 2008, 12:34
Eternal Idol eres una maquina!!!

Resulta que efectivamente, acabo d hacer una prueba con los 6 bucles for
for (i=1; i<45; i++)
    for (j=i+1; j<46; j++)
        for (k=j+1; k<47; k++)
       for (l=k+1; l<48; l++)
           for (m=l+1; m<49; m++)
               for (n=m+1; n<50; n++)

pero sin el flujo de salida y no me ha tardado ni un segundo,ademas se que se ejecutan y bien porque he estado usando puntos de ruptura, getch(); etc etc. y fenomenal,tienes toda la razon, el problema es que tengo que controlar los flujos de salida, ya sean por pantalla, en escritura o como sea.

Uno de los programas en concreto es el "miprimitiva.exe" lo puedes descargar de aqui: miprimitiva.com/descargas/ (es solo un ejecutable que no necesita instalacion) (no tengo permisos para poner el enlace completo)y si, lo que necesito es recorrerlas de principio a fin sin repetir, tal y como lo hace tu codigo. 1,2,3,4,5,6     1,2,3,4,5,7........hasta 44,45,46,47,48,49 en total 13.983.816 de combinaciones.

Al desensamblar los programas lo unico que consigo es liarme mas, porque me los dejan en ensamblador y no tengo ni idea.

Os ire contando como va quedando y como voy controlando los flujos.
Una vez mas requetegracias!!!!!!!
Título: Re: Millones de Combinaciones
Publicado por: Eternal Idol en Viernes 5 de Diciembre de 2008, 14:05
De nadas y suerte con eso  :beer: