Enumerar los subconjuntos

En esta página, aprenderás cómo generalizar la solución de helado para enumerar los subconjuntos de cualquier conjunto.

Dado un conjunto de cosas, un subconjunto contiene cero o más de sus elementos, sin duplicados. Como ocurría con los tazones de helado, el orden no importa.

{Banana, Manzana} es el mismo subconjunto que {Banana, Manzana}.

Por ejemplo, dado el conjunto {Banana, Naranja, Banana}, hay subconjuntos de un elemento como {Banana} y subconjuntos de dos elementos como {Manzana, Banana}. El conjunto original {Manzana, Naranja, Banana} cuenta, al igual que el conjunto vacío {} con cero elementos.

  1. Escribe todos los subconjuntos de {manzana, naranja, plátano}. ¿Cuántos hay?
  2. Escribe todos los subconjuntos de {Pretzel, Manzana, Naranja, Banana}. Trate de hacer esto con el menor trabajo posible.
  3. Ahora crea un bloque subsets que toma una lista como entrada y reporta una lista de listas en la que cada elemento es un subconjunto de la lista de entrada original. El orden en que aparecen los subconjuntos en la lista de salida no importa, pero cada subconjunto debe aparecer exactamente una vez. El resultado podría verse así:
    subconjuntos(lista{Manzana, Naranja, Banana}) reporta {{},{Banana}, {Naranja}, {Banana, Naranja},{Manzana}, {Manzana, Banana}, {Manzana, Naranja}, {Manzana, Naranja, Banana}}

    Si estás atascado después de probar tantas ideas que se te ocurran, haz clic aquí para obtener un poco de ayuda.

    • ¿Cuántos subconjuntos tiene el conjunto vacío {}?
    • ¿Qué deberían informar los subconjuntos en el caso base? ¡Esta es una parte difícil de hacer bien!
    • ¿Cuántos subconjuntos de {Pretzel, Manzana, Naranja, Banana} contienen Pretzel? ¿Cuántos no?
    • Describa "los subconjuntos de {Pretzel, Manzana, Naranja, Banana} que no contienen Pretzel" sin usar las palabras "no contienen".
    • Esta es una versión de cómo se vería el código, con muchos espacios para llenar…
      subconjuntos(conjunto){si(){reportar()}sino{...; reportar(anexar()())}}

Subconjuntos y eficiencia

Aquí hay una solución para el bloque subconjuntos.

subconjuntos(conjunto){si(¿vacío?(conjunto)){reportar(lista{})}sino{reportar(anexar(subconjuntos(todos menos el primero (conjunto)))(mapear(elemento(1) de (conjunto) delante de ()) sobre(subconjuntos(todos menos el primero(conjunto)))))}}

Esta solución para subconjuntos realiza la misma llamada recursiva dos veces, una ineficiencia que se puede corregir.

  1. Usar una variable conteo para contar cuántas llamadas recursivas se realizan para encontrar los 64 subconjuntos de una lista de seis elementos.
  2. Averigua cómo reducir la cantidad de llamadas recursivas evitando llamadas redundantes.