elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Como proteger una cartera - billetera de Bitcoin


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ideas para combinaciones?
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ideas para combinaciones?  (Leído 1,953 veces)
StrikeOne

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Ideas para combinaciones?
« en: 16 Junio 2012, 21:36 pm »

Hola!

Necesito generar todas las combinaciones posibles de un numero de N digitos usando solo los digitos 4 y 7.

Ejemplo:

Generar todas las combinaciones de un numero de 3 digitos usando solo 4's y 7's.

444
447
474
477
744
747
774
777

Y repetir esto hasta numeros de 30 digitos.

Alguien tiene alguna idea de como se podria hacer esto de manera eficiente? He estado pensando pero no se me ocurre nada de nada! Tengo un limite de tiempo de 8 segundos para generar todas las combinaciones.

Agradezco sugerencias e ideas!

Gracias!


« Última modificación: 16 Junio 2012, 21:40 pm por StrikeOne » En línea

noele1995

Desconectado Desconectado

Mensajes: 137



Ver Perfil
Re: Ideas para combinaciones?
« Respuesta #1 en: 17 Junio 2012, 10:36 am »

Bueno te puedo dar un par de ideas que en cuestion deberian dejarte hacer tu algoritmo, el numero de permutaciones (lo que tu buscas son permutaciones no combinaciones ya que importa el orden) posibles viene dado por la expresion:
Código:
numPermutaciones = numElecciones^numDigitos

 y en tu caso ya que el numero de elecciones no es variable (4 y 7) siempre es 2:
Código:
numPermutaciones = 2^numDigitos

Entonces ya tienes el numero de permutaciones posibles, lo suyo seria crear un array de tipo string (en cpp nose como se le llamara ya que soy soy un negado) del tamaño de numero de permutaciones
y ir rellenandolo de la siguiente forma, mitad de 7s y mitad de 4s, despues la mitad de la mitad de los que habias rellenado con 7s los rellenas con 4s ya la otra mitad de la mitad de los rellenados con 7s los rellenas de 7s. Y asi continuamente hasta tener rellenios todos, espero que la idea te ayude. No te puedo ayudar con ejemplo ya que soy un negado en cpp  :-\ :-\


En línea

El_Java

Desconectado Desconectado

Mensajes: 144



Ver Perfil WWW
Re: Ideas para combinaciones?
« Respuesta #2 en: 17 Junio 2012, 12:10 pm »

Es un problema simple de recursividad, no es necesario hacer lo que dice noele1995, sería una función del tipo:
Código:
void func (string s = ""){
   si (tamaño(s) es igual a numero_digitos) mostrar y fin;
   llamar: func(s+"4");
   llamar: func(s+"7");
  
   fin;
}

Yo ya la he hecho y me ha ocupado 3 lineas la función. Te lo escribo en pseudo-código para no hacerte el trabajo al 100%.

EDITO: Para casos grandes es ineficiente, no creo que lo haga en 8 segundos... (aunque siempre puedes precalcular)

Un saludo!
« Última modificación: 17 Junio 2012, 12:14 pm por El_Java » En línea

engel lex
Colaborador
***
Desconectado Desconectado

Mensajes: 15.347



Ver Perfil
Re: Ideas para combinaciones?
« Respuesta #3 en: 17 Junio 2012, 12:49 pm »

El_Java exacto asi es la forma que mas consumiría muchos recursos...

pero son 2 valores hasta 30 dígitos... piensa en binario y son un total de 2^30 valores hay que verle la cara (~10^9) XD... estamos hablando de MUCHOS en un procesador de 2ghz con el método que muestras tardaría un tiempo considerable... es un problema mas de eficiencia que de dificultad...


recomiendo un método al estilo binario...

que digas este numero debería ser 00001000101000 en binario, si en vez de 0 y 1 usas 4 y 7 te puede servir 44447444747444

porque necesitas por donde sea que lo vea 2 ciclos... 1 para recorrer todos los posibles valores (cuidado con overflows aquí) y un según para rellenar el valor...

serian solo en los ciclos 1er ciclo= (2^cantidad de dígitos) 2do ciclo=(cantidad de dígitos) =1er*2do =3^cantidad de digitos... 3^30 operaciones...
En línea

El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Ideas para un diseño. « 1 2 3 »
Diseño Gráfico
Vassago 20 6,545 Último mensaje 2 Noviembre 2005, 18:24 pm
por johnwmartinez
Ideas para un diseño
Diseño Gráfico
Vassago 4 1,740 Último mensaje 8 Marzo 2007, 19:37 pm
por Vassago
[Solucionado] ciclo for arrojo combinaciones, ¿?para que se almacene en la BD
PHP
~V 5 3,384 Último mensaje 20 Junio 2010, 18:48 pm
por Falso Positivo
[SOLUCIONADO] Ayuda para programar un Auto-Typer que pruebe combinaciones.
Programación General
TheJackal 7 3,715 Último mensaje 11 Julio 2010, 02:00 am
por TheJackal
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines