Tools for enumeration of all subsets of a set.
More...
Go to the source code of this file.
Detailed Description
Tools for enumeration of all subsets of a set.
 Todo:
 Concepts

A subset: a set (sequence) of iterators.

So a general concept of a set (container, sequence) is needed; or perhaps just using ranges is enough?!

An iterator over all subsets (or, for example, over all subsets of size k) dereferenced should yield the subset as an inplacemodification of some internal storage.

Identifying a subset with its characteristic function, we can use the tools from GrayCodes.hpp to enumerate all subsets (flipping only one element at a time). The iterator should made available the information about the element flipped.
 Todo:
 Organisation and connections
 Todo:
 Algorithmic framework

There should be a general algorithmic framework, allowing to run through all subsets (or "substructures"), applying an algorithm to each subset, and gathering statistics.

An application is as follows: For given n, k compute the clausesets with all kclauses over variables 1, ..., n (there should be generator for this, generalising the complete hypergraphs K_n^k). To each subclauseset apply the enumerationSATalgorithm, gathering as much information as possible (at least for each clausecount c we need the number of satisfiable clausesets  with this we can compute the probability that a random clausesequence is satisfiable).

See SATAlgorithms/EnumerationSubclausesets.hpp for a generic algorithm for clausesets. Perhaps later this framework might be generalised.
 Todo:
 Refinements

Enumerating all partial hypergraphs of a hypergraph with bipartite edgevertex graph should yield also these bipartite graphs (respectively the corresponding information) for the partial hypergraphs.

In the same vein, when enumerating all subclausesets of a clauseset (or something similar) with such an auxiliary structure, then the enumeration should (possibly) make available this structure also for the enumerated objects.
Definition in file Subsets.hpp.