Return all subsets of
such that
is true.
The boolean function must be decreasing, i.e.
if
.
This function is implemented to call as few times as possible. More
precisely,
will be called on all sets
such that
is true, as
well as on all inclusionwise minimal sets
such that
is false.
The problem that this function answers is also known as the learning problem on monotone boolean functions, or as computing the set of winning coalitions in a simple game.
INPUT:
f – a boolean function which takes as input a list of elements from X.
X – a list/iterable.
max_obstruction_size (integer) – if you know that there is
a such that
is true if and only if
is true
for all
with
, set
max_obstruction_size=k. It may dramatically decrease the
number of calls to
. Set to None by default, meaning
.
ncpus – number of cpus to use for this computation. Note that
changing the value from (default) to anything different enables
parallel computations which can have a cost by itself, so it is not
necessarily a good move. In some cases, however, it is a great move. Set
to None to automatically detect and use the maximum number of cpus
available.
Note
Parallel computations are performed through the parallel() decorator. See its documentation for more information, in particular with respect to the memory context.
EXAMPLE:
Sets whose elements all have the same remainder mod 2:
sage: from sage.combinat.subsets_hereditary import subsets_with_hereditary_property
sage: f = lambda x: (not x) or all(xx%2 == x[0]%2 for xx in x)
sage: list(subsets_with_hereditary_property(f,range(4)))
[[], [0], [1], [2], [3], [0, 2], [1, 3]]
Same, on two threads:
sage: sorted(list(subsets_with_hereditary_property(f,range(4),ncpus=2)))
[[], [0], [0, 2], [1], [1, 3], [2], [3]]
One can use this function to compute the independent sets of a graph. We
know, however, that in this case the maximum obstructions are the edges, and
have size 2. We can thus set max_obstruction_size=2, which reduces the
number of calls to from 91 to 56:
sage: num_calls=0
sage: g = graphs.PetersenGraph()
sage: def is_independent_set(S):
....: global num_calls
....: num_calls+=1
....: return g.subgraph(S).size()==0
sage: l1=list(subsets_with_hereditary_property(is_independent_set,g.vertices()))
sage: num_calls
91
sage: num_calls=0
sage: l2=list(subsets_with_hereditary_property(is_independent_set,g.vertices(),max_obstruction_size=2))
sage: num_calls
56
sage: l1==l2
True
TESTS:
sage: list(subsets_with_hereditary_property(lambda x:False,range(4)))
[]
sage: list(subsets_with_hereditary_property(lambda x:len(x)<1,range(4)))
[[]]
sage: print list(subsets_with_hereditary_property(lambda x:True,range(2)))
[[], [0], [1], [0, 1]]