Árbol de subconjuntos
Se dice que A es un subconjunto maximal de B si A ⊂ B y no existe ningún C tal que A ⊂ C y C ⊂ B. Por ejemplo, {2,5} es un subconjunto maximal de {2,3,5], pero {3] no lo es.
El árbol de los subconjuntos de un conjunto A es el árbol que tiene como raíz el conjunto A y cada nodo tiene como hijos sus subconjuntos maximales. Por ejemplo, el árbol de subconjuntos de [2,3,5] es
Usando el tipo de dato
el árbol anterior se representa por
Definir las funciones
tales que
- (arbolSubconjuntos x) es el árbol de los subconjuntos de xs. Por ejemplo,
- (nOcurrenciasArbolSubconjuntos xs ys) es el número de veces que aparece el conjunto xs en el árbol de los subconjuntos de ys. Por ejemplo,
Comprobar con QuickChek que, para todo entero positivo n, el número de ocurrencia de un subconjunto xs de [1..n] en el árbol de los subconjuntos de [1..n] es el factorial de n-k (donde k es el número de elementos de xs).
Soluciones
Pensamiento
Nunca traces tu frontera,
ni cuides de tu perfil;
todo eso es cosa de fuera.Antonio Machado