Subsets.hpp File Reference

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.

  • 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 in-place-modification 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.
Organisation and connections
Algorithmic framework
  • There should be a general algorithmic framework, allowing to run through all subsets (or "sub-structures"), applying an algorithm to each subset, and gathering statistics.
  • An application is as follows: For given n, k compute the clause-sets with all k-clauses over variables 1, ..., n (there should be generator for this, generalising the complete hypergraphs K_n^k). To each sub-clause-set apply the enumeration-SAT-algorithm, gathering as much information as possible (at least for each clause-count c we need the number of satisfiable clause-sets --- with this we can compute the probability that a random clause-sequence is satisfiable).
  • See SATAlgorithms/EnumerationSubclausesets.hpp for a generic algorithm for clause-sets. Perhaps later this framework might be generalised.
  • Enumerating all partial hypergraphs of a hypergraph with bipartite edge-vertex graph should yield also these bipartite graphs (respectively the corresponding information) for the partial hypergraphs.
  • In the same vein, when enumerating all sub-clause-sets of a clause-set (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.