Either a reference to the basic container whose lifetime is not shorter than that of the power set object,
or a "bare" container type for a temporary object.
See also the detailed discussion.
Either a functor class satisfying the extended requirements
for unary operations, or
an untyped template of such a class wrapped into BuildUnary or BuildUnaryIt
(preferably expressed via the convenience typedef from namespace polymake::operations.
This is a convenience function, which allows to embed a temporary object into an expression without writing down its exact
type. The result is identical to a direct call to the constructor of the corresponding class with the same arguments.
Please note that this and similar convenience functions always create an object parameterized with references
to the input data (containers.) Sometimes, especially in a function return statement, you will need a reference-less variant;
then you have to use the constructor.
Either a functor class satisfying the extended requirements
for binary operations, or
an untyped template of such a class wrapped into BuildBinary or BuildBinaryIt
(preferably expressed via the convenience typedef from namespace polymake::operations.
This assertion is checked only in the DIMENSION_CHECKS compilation mode.
Prerequisits
#include <PowerSet.h>
using namespace polymake;
General case
template <typename ElementType, typename ElementComparator=operations::cmp>
class PowerSet
: public Set< Set<ElementType, ElementComparator> >;
As the name says, this is a set of subsets of a base set of ElementType.
There is nothing special about this class, it was introduced mainly as a convenient shortcut for
Set< Set<ElementType> > it is derived from. Due to the
AVL tree data representation, the subsets appear in the
lexicographical order. The base set is encoded only implicitly, as a union of all contained
subsets.
The PowerSet class in its current implementation is definitely not the optimal tool
for representing a power set.
For a base set of non-negative integer numbers, you may get much better performance with a hashing
container, e.g. std_ext::hash_set<Bitset> .
PowerSet has the same set of constructors as Set;
it defines merely two own methods:
int PowerSet::insertMax(const GenericSet& s);
int PowerSet::insertMin(const GenericSet& s);
Both methods try to add s to the power set, preserving the condition that there may not
be dependent subsets (one is included in another one) among the power set elements.
Return the success code:
0
a subset equal to s was found, power set unchanged
-1
a subset including s (insertMax) or
included in s (insertMin) was found, power set unchanged
1
s added to the power set, some other subsets might have been deleted:
included in s (insertMax) or including s (insertMin.)
These methods are very expensive, as they iterate over the entire power set, performing the
inclusion test for each element.
The same functionality is implemented much more efficiently in FacetList class, but with the same restriction
as by Bitset: the base set has to be a contiguous range of non-negative integer numbers.
The following classes model power sets in some special but often occuring cases much more efficiently
than PowerSet would do.
The element subsets are not physically stored, but rather generated "on the fly" in the course
of iteration over the power set.
These constructions can be applied to every class conforming to the STL container interface.
If the base set is a GenericSet, then the resulting powerset will also belong to a GenericSet family,
since the generated subsets always appear in the lexicographical order. For the sake of brevity, we will always call the
base container as ``base set''.