Enumeración de todos los anti-cadenas en un conjunto finito

Question

Tengo algunas razonablemente pequeño finito posets (en menos de 20 puntos) y desea iterar sobre todos los "downsets" en el poset, donde un downset es un conjunto cerrado bajo ≤ (de modo que si x en X, y y ≤ x, entonces y en X). Un downset puede ser especificado (y para mis propósitos, se especifica) por un antichain (un conjunto de incomparable elementos, el máximo de elementos de la downset).

Por lo tanto, para iterar sobre todos los antichains en el poset. El poset es lo suficientemente pequeño como para iterar sobre todos los subconjuntos, pero creo que uno puede hacer mucho mejor que este.

¿Cuáles son algunos algoritmos eficientes para iterar sobre los antichains de un número finito de poset?

El poset puede ser dado (a su elección) por su transitiva reducción ("diagrama de Hasse" o "cubrir relación") o por la lista de principio downsets.

Answer 1

La obvia codiciosos retroceso enfoque parece funcionar bastante bien aquí. El fin de todos los elementos de forma arbitraria. Para cada elemento en el fin de tratar de no ponerlo en la lucha contra la cadena, y después de su hecho con esas posibilidades se trate de ponerla en el anti-cadena; en cualquier caso, continuar de forma recursiva con el siguiente elemento hasta que todos los elementos estén dentro o fuera. El truco que hace que este más rápido de sólo tratar todos los subconjuntos, es que cada vez que ponen un elemento $x$ en el subconjunto, puede filtrar los elementos restantes desechando aquellos que son comparables con $x$. Los elementos arrojados no son considerados en todo, mientras que $x$ es "en". Es útil para almacenar el conjunto de las restantes (incomparable) elementos en el punto al $x$ fue agregado, como se puede restaurar como el conjunto de candidatos siempre dando marcha atrás en un punto posterior en el tiempo al $x$ es el último elemento que permanece en el antichain.

En ningún punto de su árbol de búsqueda que se vaya a un estéril rama (no soluciones), debido a que los elementos que están en la medida en que no constituyen un válido antichain. Esto significa que el tiempo de ejecución es acotado por una constante (la profundidad) veces el número de anti-cadenas que están ahí para ser encontrado; uno no puede esperar a hacerlo mejor, a menos que exista algún argumento matemático que cuenta el antichains sin la generación de ellos.