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.combinat.backtrack.SearchForest

The set of all subsets of ambient whose elements satisfy predicate pairwise


  • 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).


in fact, predicate(x,x) is never called.


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).


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()
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
sage: P.category()
Category of finite enumerated sets


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.


Returns the children of a node in the tree.