Autor Tema: Programa que haga particiones de conjuntos

0 Usuarios y 1 Visitante están viendo este tema.

17 Marzo, 2010, 03:36 pm
Leído 1375 veces

Lina Marcela

  • $$\Large \color{red}\pi$$
  • Mensajes: 1
  • Karma: +0/-0
  • Sexo: Femenino
Hola, necesito hacer un programa que haga todas las posibles particiones de un conjunto ordenado, en cualquier programa.
Por ejemplo
\(  \left\{{a,b,c,d}\right\}=\left\{{a}\right\}\cup{\left\{{b,c,d}\right\}}=\left\{{a,b}\right\}\cup{\left\{{c,d}\right\}}=\left\{{a,b,c}\right\}\cup{\left\{{d}\right\}} \)
No puedo hacer todos los casos particulares porque mi conjunto es de 11 elementos, asi tendria muchas posibilidades, creo que son 1024.
Alguien puede ayudarme? ;)

17 Marzo, 2010, 04:33 pm
Respuesta #1

aesede

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 493
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Bienvenida al foro :)

No sé en qué lenguaje querés implementarlo. Tampoco sé si habrá un algoritmo "estandarizado" para hacerlo, pero se me ocurre ésto:

Dado un conjunto finito \( A \), con cardinal \( n \), queremos encontrar el conjunto de partes de \( A \), que denotamos por \( \mathcal{P}(A) \). Para esto cargamos todos los elementos de A en dos vectores (arrays), que vamos a llamar \( B_1 \) y \( B_2 \). Al conjunto de partes lo vamos a almacenar en otro vector, que denominamos \( P \). Entonces, cada elemento de \( P \) va a estar conformado por un elemento de \( B_1 \) y uno o más elementos de \( B_2 \).

Vamos a valernos de dos bucles, uno que vaya varíe los elementos de \( B_1 \) y otro los de \( B_2 \).

La idea, más o menos, es:

P[0] = "{}"; //caso particular 1
P[1] = "A"; //caso particular 2
k=2; //definimos a partir de qué posición del vector P empezamos a cargar conjuntos de partes

for(i=0; i<n ; i++) {

      for(j=0; j<n; j++) {

            P[k] = "B_1[i], B_2[j]";
           
            k++;

      }

}


Así, tal y como está, serviría únicamente para calcular los conjuntos de partes formados por dos elementos. Habría que ver de generalizarlo para conjuntos de partes de \( n-1 \) elementos (porque el de \( n \) elementos ya lo agregamos al principio). Está bastante incompleto el algoritmo, pero por algo se empieza. Se aceptan sugerencias ;)

No puedo hacer todos los casos particulares porque mi conjunto es de 11 elementos, asi tendria muchas posibilidades, creo que son 1024.

En realidad son 2048. El conjunto potencia contiene \( 2^n \) elementos (siendo \( n \) el cardinal del conjunto en cuestión). Es decir: \( \#A=n \Longrightarrow{} \#\mathcal{P}(A) = 2^n \).

Saludos.