Conjunto potencia

Un pequeño acertijo

Después de un tiempo sin publicar, vengo a hablarles sobre los “conjuntos potencia”. Para no empezar con definiciones tan matemáticas (al menos por ahora), comenzaré con un pequeño acertijo que dice lo siguiente: Teniendo en cuenta que una lámpara puede estar prendida o apagada y suponiendo que uno tiene un tablero con 5 lámparas numeradas: L1, L2, L3, L4 y L5 ¿Cuántas y cuáles configuraciones posibles se tienen entre las cinco lámparas teniendo en cuenta sus dos estados posibles (prendido/apagado)?

Para entender, y encarar mejor la consigna, es posible iniciar suponiendo que sólo se dispone de una lámpara, en este caso L1, que puede estar prendida o bien, apagada, por lo que las configuraciones posibles (que denotaré en forma de conjuntos con la letra C) serían: C1={}, donde el conjunto C1 vacío indica que, en este caso, no hay lámpara encendida. C2={L1}, donde la presencia de L1 indica que la lámpara prendida. Luego se tiene que C es C1 UNION C2, es decir C={{}, {L1}}

Como verán, al momento, no hay ninguna dificultad sobresaliente (si la hay, recomiendo leer aunque sea, un pequeño aproach sobre conjuntos). Con la base mencionada más arriba, es posible acercarse un poco más a la resolución de la consigna propuesta. Para ello, a las posibles configuraciones anteriores (C) se agregará L2: Obviamente esta nueva lámpara, al igual que L1, también tendrá 2 estados posibles. Si se tiene en cuenta el conjunto anterior de configuraciones, es decir C, se requieren mantener todas estas, pero adicionando la posibilidad de que L2 esté prendida en cada caso, es decir:

• C1={}. Ninguna lámpara encencida
• C2={L1}. Sólo encendida L1.
• C3={L2}. Sólo encendida L2.
• C4={L1, L2}. Ambas lámparas encedidas. O, en notación de conjuntos C={{}, {L1}, {L2}, {L1,L2}}

Cómo se puede observar, si se agrega una nueva lámpara, la cantidad de configuraciones posibles, duplica a la anterior. Lo mismo en caso de agregar L3, y luego L4. Esto significa que, con 5 lámparas, se tendrán 2*2*2*2*2=2^5 configuraciones, es decir 32 formas posibles de combinar las 5 lámparas. Encontrar todas las combinaciones posibles, proceso que puede parecer trivial, llevaría un poco de tiempo, pero, para suerte de nosotros, existe un procedimiento.

Conjunto potencia:

Las configuraciones vistas anteriormente son, con más precisión, todos los subconjuntos que parten del conjunto de lámparas. Y eso es precisamente el conjunto potencia: Un conjunto formado por todos los subconjuntos posibles de un conjunto inicial. Esto es denotado, matemáticamente, por P(A), donde A es un conjunto.

Para entrar un poquito más en el funcionamiento de P(A), es necesario analizar lo siguiente: En el ejemplo de una única lámpara, es decir de A={L1}, se obtuvo P(A)={{}, {L1}}. Ahora, si al conjunto de lámparas A, se le agregaba L2, se tenía que B era A UNION {L2}, o más obvio, B={L1, L2}. Ahora, para obtener P(B), era necesario el P(A) calculado anteriormente (para conservar las anteriores configuraciones) junto con el nuevo elemento, en este caso {L2} adjuntado a cada subconjunto de P(A). En rasgos generales: P(B)=P(A) UNION {Cada elemento de P(A) con {L2}}. En base a esto, como ya se tiene calculado P(A), reemplazando, se tiene que P(B)={{}, {L1}} UNION {Cada elemento de {{}, {L1}} con {L2}}, lo que es igual a P(B)={{}, {L1}} UNION {{L2}, {L1,L2}}, y a su vez, simplificando (o uniendo, mejor dicho), es igual a P(B)={{}, {L1}, {L2}, {L1, L2}}. De esta forma (forma que quizás haya que releerla una vez más, se calcula el conjunto potencia). Dejaré marcada esta sección con un asterisco, ya que luego la retomaré (*).

Un algoritmo para P(A)

Alejándonos un poco del acertijo (el cual ya resolveremos), es necesario un algoritmo un poco más general. La cuestión sería, entonces: Dado un conjunto A, ¿Cómo calcular P(A)?

1. Para empezar, es necesario verificar si A es vacío, ya que en este caso, casi como una obviedad, P(A)={} (el conjunto potencia del conjunto vacío es vacío).
2. Ahora bien, si el conjunto A no es vacío, se debe tomar el último elemento de A (el cual se denotará como "a", para simplificar).
3. En esta instancia, con el elemento "a" del paso 2, se debe calcular B=A-{a}. Es decir, B va a ser el conjunto A sin su último elemento.
4. Releyendo la parte remarcada en el anterior apartado (*), se tiene que es necesario calcular P(B) UNIÓN { Cada elemento de P(B) adjuntado a "a"}. Luego, se repite el paso 1, pero para calcular el necesario P(B). Ahora, por suerte, se dispone de un algoritmo que calcula el conjunto potencia (recursivo, como podrán observar) ¿Aún no están convencidos? Probemos, paso a paso, y para que no sea denso, con un conjunto de dos lámparas: Para el caso, entonces, dado L={L1, L2}, se requiere calcular P({L1,L2}).

Paso A: P({L1, L2})

• Paso A.1: Se tiene que A={L1, L2} no es vacío, entonces...
• Paso A.2: Se toma el último elemento de A, es decir L2.
• Paso A.2: Se calcula B={L1,L2}-L2, es decir, B={L1}.
• Paso A.3: Se retorna P(B) UNIÓN {Cada elemento de P(B) adjuntado a L2} (Como verán ahora es necesario calcular P(B)), en el paso B.

Paso B: Se repite el proceso, pero con P(A)=P({L1}):

• Paso B.1: Se tiene que A no es vacío, entonces...
• Paso B2: Se toma el último elemento de A, es decir L1.
• Paso B.2: Se calcula B={L1}-L1, es decir, B={}.
• Paso B.3: Se retorna P(B) UNIÓN {Cada elemento de P(B) adjuntado a L1} (Como verán es necesario calcular el P(B) de esta instancia).

Paso C: Se repite el proceso con el nuevo P(A)=P({}):

• Paso C.1: A es vacío, entonces se retorna {}.

Como se puede observar, el algoritmo es una recursividad que finaliza (o “corta”) cuando el conjunto del cual se requiere calcular la potencia es vacío (Paso C). Con esto ya hemos finalizado. Ahora, solo se requiere “unir todo”:

1. En el paso C, se retorna {} (con lo que subimos un paso en la recursividad).
2. En el paso B, se retorna {B={} UNIÓN {Cada elemento de B={} adjuntado a L1}} es decir, se retorna {{}, {L1}}
3. Ahora, un paso más arriba, en A, se retorna {B={{}, L1} UNION {Cada elemento de B={{}, L1} con L2}} = {{{}, L1} UNION {L2, {L1, L2}}}, lo que es igual a “ se retorna P(L)={{}, L1, L2, {L1, L2}}”.

Ahora, después de un ejemplo (por si estábamos descreídos), uno puede estar segurísimo que el algoritmo hace lo que se quería en principio, ya que efectivamente ¡P(L)={{}, {L1}, {L2}, {L1, L2}}!

Implementación de P(A) y resolución del acertijo

Para finalizar, volviendo al acertijo de las 5 lámparas, sería un poco denso calcular (a mano) las combinaciones de subconjuntos posibles (que en total serían 32), por lo que creo correcto implementar (en este caso en Python), el algoritmo arriba mencionado:

# Agregación de n a cada elemento de P(B)
def SP(B, n):
     for i in B:
          i.append(n)
     return B

# P(A): entrada principal.
def P(A):
     if not A:
          return [[]]
      B = A[0:len(A)-1] # B igual A menos su último elemento.
     return P(B) + SP(P(B), A[len(A)-1])

Ahora que ya se dispone de una implementación, es posible resolver el acertijo de las posibles configuraciones con 5 lámparas, más precisamente, es posible resolver P(“L1”, “L2”, “L3”, “L4”, “L5”) (Menos mal que se tiene un algoritmo, pues este es el resultado obtenido):

C=[[], ['L1'], ['L2'], ['L1', 'L2'], ['L3'], ['L1', 'L3'], ['L2', 'L3'], ['L1', 'L2', 'L3'], ['L4'], ['L1', 'L4'], ['L2', 'L4'], ['L1', 'L2', 'L4'], ['L3', 'L4'], ['L1', 'L3', 'L4'], ['L2', 'L3', 'L4'], ['L1', 'L2', 'L3', 'L4'], ['L5'], ['L1', 'L5'], ['L2', 'L5'], ['L1', 'L2', 'L5'], ['L3', 'L5'], ['L1', 'L3', 'L5'], ['L2', 'L3', 'L5'], ['L1', 'L2', 'L3', 'L5'], ['L4', 'L5'], ['L1', 'L4', 'L5'], ['L2', 'L4', 'L5'], ['L1', 'L2', 'L4', 'L5'], ['L3', 'L4', 'L5'], ['L1', 'L3', 'L4', 'L5'], ['L2', 'L3', 'L4', 'L5'], ['L1', 'L2', 'L3', 'L4', 'L5']].

Vectores booleanos

Para finalizar, quiero dejar una alternativa al algoritmo recursivo: Los vectores booleanos. Dado un arreglo, donde su tipo de índice es el conjunto en sí (es decir, el conjunto del cual se requiere calcular P(A)), su base (posibles valores del vector), estará dada por 0 (cero), en caso de que el subíndice evaluado, no forme parte del nuevo subconjunto de P(A) o 1 (uno), lo que indicará pertenencia.

Volviendo al acertijo de las lámparas, es decir, dado L1, L2, L3, L4 y L5 y dado el vector 000000, donde la primera posición refiere a L1, la segunda a L2, y así sucesivamente, se tiene que, para el caso, todas las lámparas están apagadas. Si al vector anterior (que es binario), se le adiciona un 1 (uno), se obtiene 000001, donde L5 queda encendida. En la siguiente adición de 1, al último vector obtenido, se obtiene 00010, donde sólo L4 está encendida. El proceso debiera continuar hasta 2^5 (dos elevado a la cantidad de elementos), donde la última combinación estaría dada por 11111, lo que indica que todas las lámparas se encuentran encendidas. Estas operaciones a nivel bits, se denominan bitwise. La implementación, en este caso, queda a cuenta del lector.

conjunto potencia bitwise