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 satisfy predicate pairwise

INPUT:

  • 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 of self, represented by an increasing tuple

  • rest is the set of all \(y\)’s such that \(y\) appears after \(x\) in the ambient set and predicate(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)#