Bases: sage.combinat.backtrack.SearchForest
The set of all subsets of ambient whose elements satisfy predicate pairwise
INPUT:
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(..., independant = 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.
Returns the children of a node in the tree.
TESTS:
sage: from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets
sage: def predicate(x,y): return gcd(x,y) == 1
sage: P = PairwiseCompatibleSubsets( [3,5,7,11,14], predicate); P
An enumerated set with a forest structure
sage: list(P.children( ((3,5), [14,11,7]) ))
[((3, 5, 7), (11,)), ((3, 5, 11), (14,)), ((3, 5, 14), ())]
TESTS:
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.post_process( ((4,5), (9)) )
{4, 5}
sage: P.post_process( ((4,5), ()) )
{4, 5}