The set of subsets of a finite set. The set can be given as a list or a Set
or else as an integer which encodes the set
.
See Subsets for more information and examples.
AUTHORS:
Bases: sage.structure.parent.Parent
The combinatorial class of the sub multisets of s.
EXAMPLES:
sage: S = Subsets([1,2,2,3], submultiset=True)
sage: S.cardinality()
12
sage: S.list()
[[],
[1],
[2],
[3],
[1, 2],
[1, 3],
[2, 2],
[2, 3],
[1, 2, 2],
[1, 2, 3],
[2, 2, 3],
[1, 2, 2, 3]]
sage: S.first()
[]
sage: S.last()
[1, 2, 2, 3]
Return the cardinality of self
EXAMPLES:
sage: S = Subsets([1,1,2,3],submultiset=True)
sage: S.cardinality()
12
sage: len(S.list())
12
sage: S = Subsets([1,1,2,2,3],submultiset=True)
sage: S.cardinality()
18
sage: len(S.list())
18
sage: S = Subsets([1,1,1,2,2,3],submultiset=True)
sage: S.cardinality()
24
sage: len(S.list())
24
Return the serie (here a polynom) associated to the counting of the element of self weighted by the number of element they contain.
EXAMPLES:
sage: Subsets([1,1],submultiset=True).generating_serie()
x^2 + x + 1
sage: Subsets([1,1,2,3],submultiset=True).generating_serie()
x^4 + 3*x^3 + 4*x^2 + 3*x + 1
sage: Subsets([1,1,1,2,2,3,3,4],submultiset=True).generating_serie()
x^8 + 4*x^7 + 9*x^6 + 14*x^5 + 16*x^4 + 14*x^3 + 9*x^2 + 4*x + 1
sage: S = Subsets([1,1,1,2,2,3,3,4],submultiset=True)
sage: S.cardinality()
72
sage: sum(S.generating_serie())
72
Return a random element of self with uniform law
EXAMPLES:
sage: S = Subsets([1,1,2,3], submultiset=True)
sage: S.random_element()
[2]
Bases: sage.combinat.subset.SubMultiset_s
The combinatorial class of the subsets of size k of a multiset s. Note that each subset is represented by a list of the elements rather than a set since we can have multiplicities (no multiset data structure yet in sage).
EXAMPLES:
sage: S = Subsets([1,2,3,3],2,submultiset=True)
sage: S._k
2
sage: S.cardinality()
4
sage: S.first()
[1, 2]
sage: S.last()
[3, 3]
sage: [sub for sub in S]
[[1, 2], [1, 3], [2, 3], [3, 3]]
Return the cardinality of self
EXAMPLES:
sage: S = Subsets([1,2,2,3,3,3],4,submultiset=True)
sage: S.cardinality()
5
sage: len(list(S))
5
sage: S = Subsets([1,2,2,3,3,3],3,submultiset=True)
sage: S.cardinality()
6
sage: len(list(S))
6
Return the serie (this case a polynom) associated to the counting of the element of self weighted by the number of element they contains
EXAMPLES:
sage: x = ZZ['x'].gen()
sage: l = [1,1,1,1,2,2,3]
sage: for k in xrange(len(l)):
....: S = Subsets(l,k,submultiset=True)
....: print S.generating_serie(x) == S.cardinality()*x**k
True
True
True
True
True
True
True
Return a random submultiset of given length
EXAMPLES:
sage: Subsets(7,3).random_element()
{1, 4, 7}
sage: Subsets(7,5).random_element()
{1, 3, 4, 5, 7}
Returns the combinatorial class of the subsets of the finite set s. The
set can be given as a list, Set or any iterable convertible to a set. It can
alternatively be given a non-negative integer which encode the set
(i.e. the Sage range(1,s+1)).
A second optional parameter k can be given. In this case, Subsets returns the combinatorial class of subsets of s of size k.
Finally the option submultiset allows one to deal with sets with repeated elements usually called multisets.
EXAMPLES:
sage: S = Subsets([1, 2, 3]); S
Subsets of {1, 2, 3}
sage: S.cardinality()
8
sage: S.first()
{}
sage: S.last()
{1, 2, 3}
sage: S.random_element() # random
{2}
sage: S.list()
[{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
Here is the same example where the set is given as an integer:
sage: S = Subsets(3)
sage: S.list()
[{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
We demonstrate various the effect of the various options:
sage: S = Subsets(3, 2); S
Subsets of {1, 2, 3} of size 2
sage: S.list()
[{1, 2}, {1, 3}, {2, 3}]
sage: S = Subsets([1, 2, 2], submultiset=True); S
SubMultiset of [1, 2, 2]
sage: S.list()
[[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]
sage: S = Subsets([1, 2, 2, 3], 3, submultiset=True); S
SubMultiset of [1, 2, 2, 3] of size 3
sage: S.list()
[[1, 2, 2], [1, 2, 3], [2, 2, 3]]
sage: S = Subsets(['a','b','a','b'], 2, submultiset=True); S.list()
[['a', 'a'], ['a', 'b'], ['b', 'b']]
And it is possible to play with subsets of subsets:
sage: S = Subsets(3)
sage: S2 = Subsets(S); S2
Subsets of Subsets of {1, 2, 3}
sage: S2.cardinality()
256
sage: it = iter(S2)
sage: [it.next() for _ in xrange(8)]
[{}, {{}}, {{1}}, {{2}}, {{3}}, {{1, 2}}, {{1, 3}}, {{2, 3}}]
sage: S2.random_element() # random
{{2}, {1, 2, 3}, {}}
sage: [S2.unrank(k) for k in xrange(256)] == S2.list()
True
sage: S3 = Subsets(S2)
sage: S3.cardinality()
115792089237316195423570985008687907853269984665640564039457584007913129639936
sage: S3.unrank(14123091480)
{{{1, 3}, {1, 2, 3}, {2}, {1}},
{{2}, {1, 2, 3}, {}, {1, 2}},
{},
{{2}, {1, 2, 3}, {}, {3}, {1, 2}},
{{1, 2, 3}, {}, {1}}, {{2}, {2, 3}, {}, {1, 2}}}
sage: T = Subsets(S2, 10)
sage: T.cardinality()
278826214642518400
sage: T.unrank(1441231049)
{{{3}, {1, 2}, {}, {2, 3}, {1}, {1, 3}, ..., {{2, 3}, {}}, {{}}}
Bases: sage.structure.parent.Parent
Subsets of a given set.
EXAMPLES:
sage: S = Subsets(4); S
Subsets of {1, 2, 3, 4}
sage: S.cardinality()
16
sage: Subsets(4).list()
[{}, {1}, {2}, {3}, {4},
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4},
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4},
{1, 2, 3, 4}]
sage: S = Subsets(Subsets(Subsets(GF(3)))); S
Subsets of Subsets of Subsets of Finite Field of size 3
sage: S.cardinality()
115792089237316195423570985008687907853269984665640564039457584007913129639936
sage: S.unrank(3149254230)
{{{1, 2}, {0, 1, 2}, {0, 2}, {0, 1}},
{{1, 2}, {}, {0, 2}, {1}, {0, 1, 2}, {2}},
{{1, 2}, {0}}, {{1, 2}, {0, 1}, {0, 1, 2}, {1}},
{{0, 2}, {1}}}
Returns an example of subset.
EXAMPLES:
sage: Subsets(0).an_element()
{}
sage: Subsets(3).an_element()
{1, 2}
sage: Subsets([2,4,5]).an_element()
{2, 4}
Returns the number of subsets of the set s.
This is given by .
EXAMPLES:
sage: Subsets(Set([1,2,3])).cardinality()
8
sage: Subsets([1,2,3,3]).cardinality()
8
sage: Subsets(3).cardinality()
8
alias of Set_object_enumerated
Returns the first subset of s. Since we aren’t restricted to subsets of a certain size, this is always the empty set.
EXAMPLES:
sage: Subsets([1,2,3]).first()
{}
sage: Subsets(3).first()
{}
Returns the last subset of s. Since we aren’t restricted to subsets of a certain size, this is always the set s itself.
EXAMPLES:
sage: Subsets([1,2,3]).last()
{1, 2, 3}
sage: Subsets(3).last()
{1, 2, 3}
Returns a random element of the class of subsets of s (in other words, a random subset of s).
EXAMPLES:
sage: Subsets(3).random_element() # random
{2}
sage: Subsets([4,5,6]).random_element() # random
{5}
sage: S = Subsets(Subsets(Subsets([0,1,2])))
sage: S.cardinality()
115792089237316195423570985008687907853269984665640564039457584007913129639936
sage: s = S.random_element()
sage: s # random
{{{1, 2}, {2}, {0}, {1}}, {{1, 2}, {0, 1, 2}, {0, 2}, {0}, {0, 1}}, ..., {{1, 2}, {2}, {1}}, {{2}, {0, 2}, {}, {1}}}
sage: s in S
True
Returns the rank of sub as a subset of s.
EXAMPLES:
sage: Subsets(3).rank([])
0
sage: Subsets(3).rank([1,2])
4
sage: Subsets(3).rank([1,2,3])
7
sage: Subsets(3).rank([2,3,4])
Traceback (most recent call last):
...
ValueError: {2, 3, 4} is not a subset of {1, 2, 3}
Return the set of elements.
EXAMPLES:
sage: Subsets(GF(13)).underlying_set()
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Returns the subset of s that has rank k.
EXAMPLES:
sage: Subsets(3).unrank(0)
{}
sage: Subsets([2,4,5]).unrank(1)
{2}
sage: Subsets([1,2,3]).unrank(257)
Traceback (most recent call last):
...
IndexError: index out of range
Bases: sage.combinat.subset.Subsets_s
Subsets of fixed size of a set.
EXAMPLES:
sage: S = Subsets([0,1,2,5,7], 3); S
Subsets of {0, 1, 2, 5, 7} of size 3
sage: S.cardinality()
10
sage: S.first(), S.last()
({0, 1, 2}, {2, 5, 7})
sage: S.random_element() # random
{0, 5, 7}
sage: S([0,2,7])
{0, 2, 7}
sage: S([0,3,5])
Traceback (most recent call last):
...
ValueError: {0, 3, 5} not in Subsets of {0, 1, 2, 5, 7} of size 3
sage: S([0])
Traceback (most recent call last):
...
ValueError: {0} not in Subsets of {0, 1, 2, 5, 7} of size 3
Returns an example of subset.
EXAMPLES:
sage: Subsets(0,0).an_element()
{}
sage: Subsets(3,2).an_element()
{1, 3}
sage: Subsets([2,4,5],2).an_element()
{2, 5}
EXAMPLES:
sage: Subsets(Set([1,2,3]), 2).cardinality()
3
sage: Subsets([1,2,3,3], 2).cardinality()
3
sage: Subsets([1,2,3], 1).cardinality()
3
sage: Subsets([1,2,3], 3).cardinality()
1
sage: Subsets([1,2,3], 0).cardinality()
1
sage: Subsets([1,2,3], 4).cardinality()
0
sage: Subsets(3,2).cardinality()
3
sage: Subsets(3,4).cardinality()
0
Returns the first subset of s of size k.
EXAMPLES:
sage: Subsets(Set([1,2,3]), 2).first()
{1, 2}
sage: Subsets([1,2,3,3], 2).first()
{1, 2}
sage: Subsets(3,2).first()
{1, 2}
sage: Subsets(3,4).first()
Traceback (most recent call last):
...
EmptySetError
Returns the last subset of s of size k.
EXAMPLES:
sage: Subsets(Set([1,2,3]), 2).last()
{2, 3}
sage: Subsets([1,2,3,3], 2).last()
{2, 3}
sage: Subsets(3,2).last()
{2, 3}
sage: Subsets(3,4).last()
Traceback (most recent call last):
...
EmptySetError
Returns a random element of the class of subsets of s of size k (in other words, a random subset of s of size k).
EXAMPLES:
sage: Subsets(3, 2).random_element()
{1, 2}
sage: Subsets(3,4).random_element()
Traceback (most recent call last):
...
EmptySetError
Returns the rank of sub as a subset of s of size k.
EXAMPLES:
sage: Subsets(3,2).rank([1,2])
0
sage: Subsets([2,3,4],2).rank([3,4])
2
sage: Subsets([2,3,4],2).rank([2])
Traceback (most recent call last):
...
ValueError: {2} is not a subset of length 2 of {2, 3, 4}
sage: Subsets([2,3,4],4).rank([2,3,4,5])
Traceback (most recent call last):
...
ValueError: {2, 3, 4, 5} is not a subset of length 4 of {2, 3, 4}
Returns the subset of s that has rank k.
EXAMPLES:
sage: Subsets(3,2).unrank(0)
{1, 2}
sage: Subsets([2,4,5],2).unrank(0)
{2, 4}
sage: Subsets([1,2,8],3).unrank(42)
Traceback (most recent call last):
...
IndexError: index out of range
Return a list whose elements are the elements of i of d repeated with multiplicity d[i].
EXAMPLES:
sage: from sage.combinat.subset import dict_to_list
sage: dict_to_list({'a':1, 'b':3})
['a', 'b', 'b', 'b']
Return a dictionnary whose keys are the elements of l and values are the multiplicity they appear in l.
EXAMPLES:
sage: from sage.combinat.subset import list_to_dict
sage: list_to_dict(['a', 'b', 'b', 'b'])
{'a': 1, 'b': 3}