|
Título: Ideas para combinaciones? Publicado por: StrikeOne 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! Título: Re: Ideas para combinaciones? Publicado por: noele1995 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 :-\ :-\ Título: Re: Ideas para combinaciones? Publicado por: El_Java 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 = ""){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! Título: Re: Ideas para combinaciones? Publicado por: engel lex 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... |