miércoles, 15 de enero de 2014

Algoritmo para calcular los subconjuntos de un conjunto

A veces, para resolver un problema, nos encontramos con la necesidad de calcular todos los subconjuntos posibles de un conjunto. En esta entra de blog vamos a ver un algoritmo que realiza este cálculo. Si tenemos el conjunto {a, b, c}, el conjunto de todos los subconjuntos posibles sería {{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} (ocho elementos, o 2^3, tal y como esperábamos). Nuestra amiga la recursividad nos puede dar una solución muy bonita a este problema.
Primero vamos a definir una función F que dado un conjunto de subconjuntos, y un elemento, añada ese elemento a todos los subconjuntos. El cómo trabaja esta función es más fácil de entender con un ejemplo: si tenemos el siguiente conjunto de conjuntos X={{},{a},{b}} y el elemento c, tendríamos que F(X, c) = {{c},{a,c},{b,c}}. Es decir, hemos añadido c a cada uno de los subconjuntos contenidos en X.
Lo segundo que necesitamos es una condición de parada de la recursividad. En este caso vamos a parar cuando nos pregunten los subconjuntos del conjunto vacío, que sólo tiene un elemento (2^0 es 1, ¿verdad?), a saber, el conjunto formado por el conjunto vacío. Ojo, no es lo mismo el conjunto vacío {}, que el conjunto formado por el conjunto vacío {{}}, ya que F({}, a) = {} y F({{}}, a) = {{a}}.
Ya tendríamos todo lo necesario para dar el algoritmo recursivo:
función subconj(S)
    si S = {} entonces
        retorna {{}}
    si no
        T  ← S menos e
        PT ← subconj(T)
        retorna PT unión F(PT, e)
Si lo que tenemos es el conjunto vacío {}, retornamos el conjunto formado por el conjunto vacío {{}}, tal y como habíamos dicho. Y si lo que tenemos es un conjunto no vacío, lo que hay que hacer es quitarle un elemento e cualquiera (S menos e), calcular los subconjuntos de este nuevo conjunto más pequeño (PT), y retornar estos subconjuntos junto con otra copia de ellos mismos a los que les habremos añadido el elemento e. Así si PT := {{},{a}} tenemos que PT unión F(PT, b) = {{},{a},{b},{a,b}}.
Yo creo que todo este galimatías que se forma cuando hablamos de conjuntos se debe fundamentalmente a un problema de notación, o a que no entendemos bien el concepto de conjunto. A modo de ejemplo tenemos la paradoja de Bertrand Russell, que define M como el conjunto de todos los conjuntos que no son subconjuntos de sí mismos, y a continuación se pregunta si M pertenece a sí mismo. Si respondemos que sí tenemos que no debería pertenecer, pero si respondemos que no, sí que debería pertenecer. Luego aquí hay algo que no está funcionando bien.

No hay comentarios:

Publicar un comentario