Rincón Matemático
Disciplinas relacionadas y temas generales => Computación e Informática => Mensaje iniciado por: Lina Marcela en 17 Marzo, 2010, 03:36 pm
-
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? ;)
-
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.