Subsets whose elements satisfy a predicate pairwise¶
- class sage.combinat.subsets_pairwise.PairwiseCompatibleSubsets(ambient, predicate, maximal=False, element_class=<class 'sage.sets.set.Set_object_enumerated'>)¶
Bases:
sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_forest
The set of all subsets of
ambient
whose elements satisfypredicate
pairwiseINPUT:
ambient
– a set (or iterable)predicate
– a binary predicate
Assumptions:
predicate
is symmetric (predicate(x,y) == predicate(y,x)
) and reflexive (predicate(x,x) == True
).Note
in fact,
predicate(x,x)
is never called.Warning
The current name is suboptimal and is subject to change. Suggestions for a good name, and a good user entry point are welcome. Maybe
Subsets(..., independent = predicate)
.EXAMPLES:
We construct the set of all subsets of \(\{4,5,6,8,9\}\) whose elements are pairwise relatively prime:
sage: from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets sage: def predicate(x,y): return gcd(x,y) == 1 sage: P = PairwiseCompatibleSubsets( [4,5,6,8,9], predicate); P An enumerated set with a forest structure sage: P.list() [{}, {4}, {4, 5}, {9, 4, 5}, {9, 4}, {5}, {5, 6}, {8, 5}, {8, 9, 5}, {9, 5}, {6}, {8}, {8, 9}, {9}] sage: P.cardinality() 14 sage: P.category() Category of finite enumerated sets
Here we consider only those subsets which are maximal for inclusion (not yet implemented):
sage: P = PairwiseCompatibleSubsets( [4,5,6,8,9], predicate, maximal = True); P An enumerated set with a forest structure sage: P.list() # todo: not implemented [{9, 4, 5}, {5, 6}, {8, 9, 5}] sage: P.cardinality() # todo: not implemented 14 sage: P.category() Category of finite enumerated sets
Algorithm
In the following, we order the elements of the ambient set by order of apparition. The elements of
self
are generated by organizing them in a search tree. Each node of this tree is of the form(subset, rest)
, where:subset
represents an element ofself
, represented by an increasing tuplerest
is the set of all \(y\)’s such that \(y\) appears after \(x\) in the ambient set andpredicate(x,y)
holds, represented by a decreasing tuple
The root of this tree is
( (), ambient )
. All the other elements are generated by recursive depth first search, which gives lexicographic order.- children(subset_rest)¶
Returns the children of a node in the tree.
- post_process(subset_rest)¶