SoloCodigo

Programación General => C/C++ => Visual C++ => Mensaje iniciado por: nomaskes en Domingo 27 de Agosto de 2006, 22:58

Título: Ayuda Con Programa Conjunto Potencia
Publicado por: nomaskes en Domingo 27 de Agosto de 2006, 22:58

Tengo un problema, necesito diseñar un programa que dependiendo del numero entero del 1 al 9 que se ingrese, genere todos los subconjuntos que contiene, por ejemplo:

n=3  A={1,2,3}

P(A)={{}{1}{2}{3}{1,2}{2,3}{3,1}{1,2,3}}

El problema es que tiene que ser de manera recursiva, no iterativa como seria mas facil...

Agredeceria mucho si alguien me pudiera ayudar...

Título: Re: Ayuda Con Programa Conjunto Potencia
Publicado por: chimps en Lunes 28 de Agosto de 2006, 02:38

podes aplicar una tecnica conocida como backtracking para generar todas las secuencias de un tamaño predeterminado posibles entre esos elementos de tu lista...por ejemplo, si tu lista es {1,2,3} y queres saber cuales son todas las secuencias de tamaño 2, estas serian:
<(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)>

El pseudo-codigo de un algoritmo para hacer esto seria asi:

Código: Text

1.  
2. // n en el ejemplo anterior seria 2 (tamaño de la secuencia)
3. Lista L, entero n;
4. void generar(Secuencia s) {
5.  
6.   for(cada elemento l de la lista L)
7.   {
8.     agregar l al final de la secuencia s;
9.     if(s.tamaño() = = n)
10.       imprimir(secuencia s);
11.     else
12.       generar(s);
13.    
14.     borrar l del final de la secuencia s;
15.  
16.   }
17. }
18.  
19.  

Podes seguir lo que va haciendo este algoritmo con un arbol. El nodo raiz seria vacio, despues sus hijos inmediatos serian 1, 2, 3 luego cada uno de esos nodos tendria a su vez 1, 2, 3 como hijos...este algoritmo indirectamente va armando ese arbol luego recorre para atras, armando las secuencias. Parece complicado pero si agarras un lapiz y papel para seguir el algoritmo, vas a ver como va generando la lista.

pd. podes tomar este algoritmo como base para hacer el tuyo, que note que por ejemplo no toma en cuenta todos los subconjuntos posibles (ej. solo muestra {1,2} y no {2,1}, no muestra los subconjuntos formados por si mismos: {1,1}, etc).