Subsets#
The set of subsets of a finite set. The set can be given as a list or a Set
or else as an integer \(n\) which encodes the set \(\{1,2,...,n\}\).
See Subsets
for more information and examples.
AUTHORS:
Mike Hansen: initial version
Florent Hivert (2009/02/06): doc improvements + new methods
- class sage.combinat.subset.SubMultiset_s(s)[source]#
Bases:
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]
>>> from sage.all import * >>> S = Subsets([Integer(1),Integer(2),Integer(2),Integer(3)], submultiset=True) >>> S.cardinality() 12 >>> 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]] >>> S.first() [] >>> S.last() [1, 2, 2, 3]
- cardinality()[source]#
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
>>> from sage.all import * >>> S = Subsets([Integer(1),Integer(1),Integer(2),Integer(3)],submultiset=True) >>> S.cardinality() 12 >>> len(S.list()) 12 >>> S = Subsets([Integer(1),Integer(1),Integer(2),Integer(2),Integer(3)],submultiset=True) >>> S.cardinality() 18 >>> len(S.list()) 18 >>> S = Subsets([Integer(1),Integer(1),Integer(1),Integer(2),Integer(2),Integer(3)],submultiset=True) >>> S.cardinality() 24 >>> len(S.list()) 24
- element_class#
alias of
list
- generating_serie(variable='x')[source]#
Return the polynomial associated to the counting of the elements 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
>>> from sage.all import * >>> Subsets([Integer(1),Integer(1)],submultiset=True).generating_serie() x^2 + x + 1 >>> Subsets([Integer(1),Integer(1),Integer(2),Integer(3)],submultiset=True).generating_serie() x^4 + 3*x^3 + 4*x^2 + 3*x + 1 >>> Subsets([Integer(1),Integer(1),Integer(1),Integer(2),Integer(2),Integer(3),Integer(3),Integer(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 >>> S = Subsets([Integer(1),Integer(1),Integer(1),Integer(2),Integer(2),Integer(3),Integer(3),Integer(4)],submultiset=True) >>> S.cardinality() 72 >>> sum(S.generating_serie()) 72
- random_element()[source]#
Return a random element of
self
with uniform law.EXAMPLES:
sage: S = Subsets([1,1,2,3], submultiset=True) sage: s = S.random_element() sage: s in S True
>>> from sage.all import * >>> S = Subsets([Integer(1),Integer(1),Integer(2),Integer(3)], submultiset=True) >>> s = S.random_element() >>> s in S True
- class sage.combinat.subset.SubMultiset_sk(s, k)[source]#
Bases:
SubMultiset_s
The combinatorial class of the subsets of size
k
of a multisets
. 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]]
>>> from sage.all import * >>> S = Subsets([Integer(1),Integer(2),Integer(3),Integer(3)],Integer(2),submultiset=True) >>> S._k 2 >>> S.cardinality() 4 >>> S.first() [1, 2] >>> S.last() [3, 3] >>> [sub for sub in S] [[1, 2], [1, 3], [2, 3], [3, 3]]
- cardinality()[source]#
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
>>> from sage.all import * >>> S = Subsets([Integer(1),Integer(2),Integer(2),Integer(3),Integer(3),Integer(3)],Integer(4),submultiset=True) >>> S.cardinality() 5 >>> len(list(S)) 5 >>> S = Subsets([Integer(1),Integer(2),Integer(2),Integer(3),Integer(3),Integer(3)],Integer(3),submultiset=True) >>> S.cardinality() 6 >>> len(list(S)) 6
- generating_serie(variable='x')[source]#
Return the polynomial associated to the counting of the elements of
self
weighted by the number of elements they containsEXAMPLES:
sage: x = ZZ['x'].gen() sage: l = [1,1,1,1,2,2,3] sage: for k in range(len(l)): ....: S = Subsets(l,k,submultiset=True) ....: print(S.generating_serie('x') == S.cardinality()*x**k) True True True True True True True
>>> from sage.all import * >>> x = ZZ['x'].gen() >>> l = [Integer(1),Integer(1),Integer(1),Integer(1),Integer(2),Integer(2),Integer(3)] >>> for k in range(len(l)): ... S = Subsets(l,k,submultiset=True) ... print(S.generating_serie('x') == S.cardinality()*x**k) True True True True True True True
- random_element()[source]#
Return a random submultiset of given length.
EXAMPLES:
sage: s = Subsets(7,3).random_element() sage: s in Subsets(7,3) True sage: s = Subsets(7,5).random_element() sage: s in Subsets(7,5) True
>>> from sage.all import * >>> s = Subsets(Integer(7),Integer(3)).random_element() >>> s in Subsets(Integer(7),Integer(3)) True >>> s = Subsets(Integer(7),Integer(5)).random_element() >>> s in Subsets(Integer(7),Integer(5)) True
- sage.combinat.subset.Subsets(s, k=None, submultiset=False)[source]#
Return 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. Alternatively, a non-negative integer \(n\) can be provided in place ofs
; in this case, the result is the combinatorial class of the subsets of the set \(\{1,2,\dots,n\}\) (i.e. of the Sagerange(1,n+1)
).A second optional parameter
k
can be given. In this case,Subsets
returns the combinatorial class of subsets ofs
of sizek
.Warning
The subsets are returned as Sets. Do not assume that these Sets are ordered; they often are not! (E.g.,
Subsets(10).list()[619]
returns{10, 4, 5, 6, 7}
on my system.) SeeSubsetsSorted
for a similar class which returns the subsets as sorted tuples.Finally the option
submultiset
allows one to deal with sets with repeated elements, usually called multisets. The method then returns the class of all multisets in which every element is contained at most as often as it is contained ins
. These multisets are encoded as lists.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() in S True sage: S.list() [{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
>>> from sage.all import * >>> S = Subsets([Integer(1), Integer(2), Integer(3)]); S Subsets of {1, 2, 3} >>> S.cardinality() 8 >>> S.first() {} >>> S.last() {1, 2, 3} >>> S.random_element() in S True >>> 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}]
>>> from sage.all import * >>> S = Subsets(Integer(3)) >>> 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']]
>>> from sage.all import * >>> S = Subsets(Integer(3), Integer(2)); S Subsets of {1, 2, 3} of size 2 >>> S.list() [{1, 2}, {1, 3}, {2, 3}] >>> S = Subsets([Integer(1), Integer(2), Integer(2)], submultiset=True); S SubMultiset of [1, 2, 2] >>> S.list() [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]] >>> S = Subsets([Integer(1), Integer(2), Integer(2), Integer(3)], Integer(3), submultiset=True); S SubMultiset of [1, 2, 2, 3] of size 3 >>> S.list() [[1, 2, 2], [1, 2, 3], [2, 2, 3]] >>> S = Subsets(['a','b','a','b'], Integer(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: [next(it) for _ in range(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 range(256)] == S2.list() True sage: S3 = Subsets(S2) sage: S3.cardinality() 115792089237316195423570985008687907853269984665640564039457584007913129639936 sage: S3.unrank(14123091480) # random {{{2}, {1, 2, 3}, {1, 2}, {3}, {}}, {{1, 2, 3}, {2}, {1}, {1, 3}}, {{}, {2}, {2, 3}, {1, 2}}, {{}, {2}, {1, 2, 3}, {1, 2}}, {}, {{}, {1}, {1, 2, 3}}} sage: T = Subsets(S2, 10) sage: T.cardinality() 278826214642518400 sage: T.unrank(1441231049) # random {{{1, 2, 3}, {2}, {2, 3}}, {{3}, {1, 3}, ..., {3}, {1}, {}, {1, 3}}}
>>> from sage.all import * >>> S = Subsets(Integer(3)) >>> S2 = Subsets(S); S2 Subsets of Subsets of {1, 2, 3} >>> S2.cardinality() 256 >>> it = iter(S2) >>> [next(it) for _ in range(Integer(8))] [{}, {{}}, {{1}}, {{2}}, {{3}}, {{1, 2}}, {{1, 3}}, {{2, 3}}] >>> S2.random_element() # random {{2}, {1, 2, 3}, {}} >>> [S2.unrank(k) for k in range(Integer(256))] == S2.list() True >>> S3 = Subsets(S2) >>> S3.cardinality() 115792089237316195423570985008687907853269984665640564039457584007913129639936 >>> S3.unrank(Integer(14123091480)) # random {{{2}, {1, 2, 3}, {1, 2}, {3}, {}}, {{1, 2, 3}, {2}, {1}, {1, 3}}, {{}, {2}, {2, 3}, {1, 2}}, {{}, {2}, {1, 2, 3}, {1, 2}}, {}, {{}, {1}, {1, 2, 3}}} >>> T = Subsets(S2, Integer(10)) >>> T.cardinality() 278826214642518400 >>> T.unrank(Integer(1441231049)) # random {{{1, 2, 3}, {2}, {2, 3}}, {{3}, {1, 3}, ..., {3}, {1}, {}, {1, 3}}}
- class sage.combinat.subset.SubsetsSorted(s)[source]#
Bases:
Subsets_s
Lightweight class of all subsets of some set \(S\), with each subset being encoded as a sorted tuple.
Used to model indices of algebras given by subsets (so we don’t have to explicitly build all \(2^n\) subsets in memory). For example,
CliffordAlgebra
.- element_class#
alias of
tuple
- first()[source]#
Return the first element of
self
.EXAMPLES:
sage: from sage.combinat.subset import SubsetsSorted sage: S = SubsetsSorted(range(3)) sage: S.first() ()
>>> from sage.all import * >>> from sage.combinat.subset import SubsetsSorted >>> S = SubsetsSorted(range(Integer(3))) >>> S.first() ()
- last()[source]#
Return the last element of
self
.EXAMPLES:
sage: from sage.combinat.subset import SubsetsSorted sage: S = SubsetsSorted(range(3)) sage: S.last() (0, 1, 2)
>>> from sage.all import * >>> from sage.combinat.subset import SubsetsSorted >>> S = SubsetsSorted(range(Integer(3))) >>> S.last() (0, 1, 2)
- random_element()[source]#
Return a random element of
self
.EXAMPLES:
sage: from sage.combinat.subset import SubsetsSorted sage: S = SubsetsSorted(range(3)) sage: isinstance(S.random_element(), tuple) True
>>> from sage.all import * >>> from sage.combinat.subset import SubsetsSorted >>> S = SubsetsSorted(range(Integer(3))) >>> isinstance(S.random_element(), tuple) True
- unrank(r)[source]#
Return the subset which has rank
r
.EXAMPLES:
sage: from sage.combinat.subset import SubsetsSorted sage: S = SubsetsSorted(range(3)) sage: S.unrank(4) (0, 1)
>>> from sage.all import * >>> from sage.combinat.subset import SubsetsSorted >>> S = SubsetsSorted(range(Integer(3))) >>> S.unrank(Integer(4)) (0, 1)
- class sage.combinat.subset.Subsets_s(s)[source]#
Bases:
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) # random {{{1}, {0, 2}}, {{0, 1, 2}, {0, 1}, {1}, {1, 2}}, {{2}, {1, 2}, {0, 1, 2}, {0, 2}, {1}, {}}, {{1, 2}, {0}}, {{0, 1, 2}, {0, 1}, {0, 2}, {1, 2}}}
>>> from sage.all import * >>> S = Subsets(Integer(4)); S Subsets of {1, 2, 3, 4} >>> S.cardinality() 16 >>> Subsets(Integer(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}] >>> S = Subsets(Subsets(Subsets(GF(Integer(3))))); S Subsets of Subsets of Subsets of Finite Field of size 3 >>> S.cardinality() 115792089237316195423570985008687907853269984665640564039457584007913129639936 >>> S.unrank(Integer(3149254230)) # random {{{1}, {0, 2}}, {{0, 1, 2}, {0, 1}, {1}, {1, 2}}, {{2}, {1, 2}, {0, 1, 2}, {0, 2}, {1}, {}}, {{1, 2}, {0}}, {{0, 1, 2}, {0, 1}, {0, 2}, {1, 2}}}
- cardinality()[source]#
Return the number of subsets of the set
s
.This is given by \(2^{|s|}\).
EXAMPLES:
sage: Subsets(Set([1,2,3])).cardinality() 8 sage: Subsets([1,2,3,3]).cardinality() 8 sage: Subsets(3).cardinality() 8
>>> from sage.all import * >>> Subsets(Set([Integer(1),Integer(2),Integer(3)])).cardinality() 8 >>> Subsets([Integer(1),Integer(2),Integer(3),Integer(3)]).cardinality() 8 >>> Subsets(Integer(3)).cardinality() 8
- element_class[source]#
alias of
Set_object_enumerated
- first()[source]#
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() {}
>>> from sage.all import * >>> Subsets([Integer(1),Integer(2),Integer(3)]).first() {} >>> Subsets(Integer(3)).first() {}
- last()[source]#
Return the last subset of
s
. Since we aren’t restricted to subsets of a certain size, this is always the sets
itself.EXAMPLES:
sage: Subsets([1,2,3]).last() {1, 2, 3} sage: Subsets(3).last() {1, 2, 3}
>>> from sage.all import * >>> Subsets([Integer(1),Integer(2),Integer(3)]).last() {1, 2, 3} >>> Subsets(Integer(3)).last() {1, 2, 3}
- lattice()[source]#
Return the lattice of subsets ordered by containment.
EXAMPLES:
sage: X = Subsets([7,8,9]) sage: X.lattice() # needs sage.combinat sage.graphs Finite lattice containing 8 elements sage: Y = Subsets(0) sage: Y.lattice() # needs sage.combinat sage.graphs Finite lattice containing 1 elements
>>> from sage.all import * >>> X = Subsets([Integer(7),Integer(8),Integer(9)]) >>> X.lattice() # needs sage.combinat sage.graphs Finite lattice containing 8 elements >>> Y = Subsets(Integer(0)) >>> Y.lattice() # needs sage.combinat sage.graphs Finite lattice containing 1 elements
- random_element()[source]#
Return a random element of the class of subsets of
s
(in other words, a random subset ofs
).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
>>> from sage.all import * >>> Subsets(Integer(3)).random_element() # random {2} >>> Subsets([Integer(4),Integer(5),Integer(6)]).random_element() # random {5} >>> S = Subsets(Subsets(Subsets([Integer(0),Integer(1),Integer(2)]))) >>> S.cardinality() 115792089237316195423570985008687907853269984665640564039457584007913129639936 >>> s = S.random_element() >>> 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}}} >>> s in S True
- rank(sub)[source]#
Return the rank of
sub
as a subset ofs
.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}
>>> from sage.all import * >>> Subsets(Integer(3)).rank([]) 0 >>> Subsets(Integer(3)).rank([Integer(1),Integer(2)]) 4 >>> Subsets(Integer(3)).rank([Integer(1),Integer(2),Integer(3)]) 7 >>> Subsets(Integer(3)).rank([Integer(2),Integer(3),Integer(4)]) Traceback (most recent call last): ... ValueError: {2, 3, 4} is not a subset of {1, 2, 3}
- underlying_set()[source]#
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}
>>> from sage.all import * >>> Subsets(GF(Integer(13))).underlying_set() {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
- unrank(r)[source]#
Return the subset of
s
that has rankk
.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
>>> from sage.all import * >>> Subsets(Integer(3)).unrank(Integer(0)) {} >>> Subsets([Integer(2),Integer(4),Integer(5)]).unrank(Integer(1)) {2} >>> Subsets([Integer(1),Integer(2),Integer(3)]).unrank(Integer(257)) Traceback (most recent call last): ... IndexError: index out of range
- class sage.combinat.subset.Subsets_sk(s, k)[source]#
Bases:
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
>>> from sage.all import * >>> S = Subsets([Integer(0),Integer(1),Integer(2),Integer(5),Integer(7)], Integer(3)); S Subsets of {0, 1, 2, 5, 7} of size 3 >>> S.cardinality() 10 >>> S.first(), S.last() ({0, 1, 2}, {2, 5, 7}) >>> S.random_element() # random {0, 5, 7} >>> S([Integer(0),Integer(2),Integer(7)]) {0, 2, 7} >>> S([Integer(0),Integer(3),Integer(5)]) Traceback (most recent call last): ... ValueError: {0, 3, 5} not in Subsets of {0, 1, 2, 5, 7} of size 3 >>> S([Integer(0)]) Traceback (most recent call last): ... ValueError: {0} not in Subsets of {0, 1, 2, 5, 7} of size 3
- an_element()[source]#
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}
>>> from sage.all import * >>> Subsets(Integer(0),Integer(0)).an_element() {} >>> Subsets(Integer(3),Integer(2)).an_element() {1, 3} >>> Subsets([Integer(2),Integer(4),Integer(5)],Integer(2)).an_element() {2, 5}
- cardinality()[source]#
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
>>> from sage.all import * >>> Subsets(Set([Integer(1),Integer(2),Integer(3)]), Integer(2)).cardinality() 3 >>> Subsets([Integer(1),Integer(2),Integer(3),Integer(3)], Integer(2)).cardinality() 3 >>> Subsets([Integer(1),Integer(2),Integer(3)], Integer(1)).cardinality() 3 >>> Subsets([Integer(1),Integer(2),Integer(3)], Integer(3)).cardinality() 1 >>> Subsets([Integer(1),Integer(2),Integer(3)], Integer(0)).cardinality() 1 >>> Subsets([Integer(1),Integer(2),Integer(3)], Integer(4)).cardinality() 0 >>> Subsets(Integer(3),Integer(2)).cardinality() 3 >>> Subsets(Integer(3),Integer(4)).cardinality() 0
- first()[source]#
Return 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
>>> from sage.all import * >>> Subsets(Set([Integer(1),Integer(2),Integer(3)]), Integer(2)).first() {1, 2} >>> Subsets([Integer(1),Integer(2),Integer(3),Integer(3)], Integer(2)).first() {1, 2} >>> Subsets(Integer(3),Integer(2)).first() {1, 2} >>> Subsets(Integer(3),Integer(4)).first() Traceback (most recent call last): ... EmptySetError
- last()[source]#
Return 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
>>> from sage.all import * >>> Subsets(Set([Integer(1),Integer(2),Integer(3)]), Integer(2)).last() {2, 3} >>> Subsets([Integer(1),Integer(2),Integer(3),Integer(3)], Integer(2)).last() {2, 3} >>> Subsets(Integer(3),Integer(2)).last() {2, 3} >>> Subsets(Integer(3),Integer(4)).last() Traceback (most recent call last): ... EmptySetError
- random_element()[source]#
Return a random element of the class of subsets of
s
of sizek
(in other words, a random subset ofs
of sizek
).EXAMPLES:
sage: s = Subsets(3, 2).random_element() sage: s in Subsets(3, 2) True sage: Subsets(3,4).random_element() Traceback (most recent call last): ... EmptySetError
>>> from sage.all import * >>> s = Subsets(Integer(3), Integer(2)).random_element() >>> s in Subsets(Integer(3), Integer(2)) True >>> Subsets(Integer(3),Integer(4)).random_element() Traceback (most recent call last): ... EmptySetError
- rank(sub)[source]#
Return the rank of
sub
as a subset ofs
of sizek
.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}
>>> from sage.all import * >>> Subsets(Integer(3),Integer(2)).rank([Integer(1),Integer(2)]) 0 >>> Subsets([Integer(2),Integer(3),Integer(4)],Integer(2)).rank([Integer(3),Integer(4)]) 2 >>> Subsets([Integer(2),Integer(3),Integer(4)],Integer(2)).rank([Integer(2)]) Traceback (most recent call last): ... ValueError: {2} is not a subset of length 2 of {2, 3, 4} >>> Subsets([Integer(2),Integer(3),Integer(4)],Integer(4)).rank([Integer(2),Integer(3),Integer(4),Integer(5)]) Traceback (most recent call last): ... ValueError: {2, 3, 4, 5} is not a subset of length 4 of {2, 3, 4}
- unrank(r)[source]#
Return the subset of
s
of sizek
that has rankr
.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
>>> from sage.all import * >>> Subsets(Integer(3),Integer(2)).unrank(Integer(0)) {1, 2} >>> Subsets([Integer(2),Integer(4),Integer(5)],Integer(2)).unrank(Integer(0)) {2, 4} >>> Subsets([Integer(1),Integer(2),Integer(8)],Integer(3)).unrank(Integer(42)) Traceback (most recent call last): ... IndexError: index out of range
- sage.combinat.subset.dict_to_list(d)[source]#
Return a list whose elements are the elements of
i
ofd
repeated with multiplicityd[i]
.EXAMPLES:
sage: from sage.combinat.subset import dict_to_list sage: dict_to_list({'a':1, 'b':3}) ['a', 'b', 'b', 'b']
>>> from sage.all import * >>> from sage.combinat.subset import dict_to_list >>> dict_to_list({'a':Integer(1), 'b':Integer(3)}) ['a', 'b', 'b', 'b']
- sage.combinat.subset.list_to_dict(l)[source]#
Return a dictionary of multiplicities and the list of its keys.
INPUT:
a list
l
with possibly repeated elementsThe keys are the elements of
l
(in the same order in which they appear) and values are the multiplicities of each element inl
.EXAMPLES:
sage: from sage.combinat.subset import list_to_dict sage: list_to_dict(['a', 'b', 'b', 'b']) ({'a': 1, 'b': 3}, ['a', 'b'])
>>> from sage.all import * >>> from sage.combinat.subset import list_to_dict >>> list_to_dict(['a', 'b', 'b', 'b']) ({'a': 1, 'b': 3}, ['a', 'b'])
- sage.combinat.subset.powerset(X)[source]#
Iterator over the list of all subsets of the iterable
X
, in no particular order. Each list appears exactly once, up to order.INPUT:
X
– an iterable
OUTPUT: iterator of lists
EXAMPLES:
sage: list(powerset([1,2,3])) [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] sage: [z for z in powerset([0,[1,2]])] [[], [0], [[1, 2]], [0, [1, 2]]]
>>> from sage.all import * >>> list(powerset([Integer(1),Integer(2),Integer(3)])) [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] >>> [z for z in powerset([Integer(0),[Integer(1),Integer(2)]])] [[], [0], [[1, 2]], [0, [1, 2]]]
Iterating over the power set of an infinite set is also allowed:
sage: i = 0 sage: L = [] sage: for x in powerset(ZZ): ....: if i > 10: ....: break ....: else: ....: i += 1 ....: L.append(x) sage: print(" ".join(str(x) for x in L)) [] [0] [1] [0, 1] [-1] [0, -1] [1, -1] [0, 1, -1] [2] [0, 2] [1, 2]
>>> from sage.all import * >>> i = Integer(0) >>> L = [] >>> for x in powerset(ZZ): ... if i > Integer(10): ... break ... else: ... i += Integer(1) ... L.append(x) >>> print(" ".join(str(x) for x in L)) [] [0] [1] [0, 1] [-1] [0, -1] [1, -1] [0, 1, -1] [2] [0, 2] [1, 2]
You may also use subsets as an alias for powerset:
sage: subsets([1,2,3]) <generator object ...powerset at 0x...> sage: list(subsets([1,2,3])) [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] The reason we return lists instead of sets is that the elements of sets must be hashable and many structures on which one wants the powerset consist of non-hashable objects.
>>> from sage.all import * >>> subsets([Integer(1),Integer(2),Integer(3)]) <generator object ...powerset at 0x...> >>> list(subsets([Integer(1),Integer(2),Integer(3)])) [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] The reason we return lists instead of sets is that the elements of sets must be hashable and many structures on which one wants the powerset consist of non-hashable objects.
AUTHORS:
William Stein
Nils Bruin (2006-12-19): rewrite to work for not-necessarily finite objects X.
- sage.combinat.subset.subsets(X)[source]#
Iterator over the list of all subsets of the iterable
X
, in no particular order. Each list appears exactly once, up to order.INPUT:
X
– an iterable
OUTPUT: iterator of lists
EXAMPLES:
sage: list(powerset([1,2,3])) [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] sage: [z for z in powerset([0,[1,2]])] [[], [0], [[1, 2]], [0, [1, 2]]]
>>> from sage.all import * >>> list(powerset([Integer(1),Integer(2),Integer(3)])) [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] >>> [z for z in powerset([Integer(0),[Integer(1),Integer(2)]])] [[], [0], [[1, 2]], [0, [1, 2]]]
Iterating over the power set of an infinite set is also allowed:
sage: i = 0 sage: L = [] sage: for x in powerset(ZZ): ....: if i > 10: ....: break ....: else: ....: i += 1 ....: L.append(x) sage: print(" ".join(str(x) for x in L)) [] [0] [1] [0, 1] [-1] [0, -1] [1, -1] [0, 1, -1] [2] [0, 2] [1, 2]
>>> from sage.all import * >>> i = Integer(0) >>> L = [] >>> for x in powerset(ZZ): ... if i > Integer(10): ... break ... else: ... i += Integer(1) ... L.append(x) >>> print(" ".join(str(x) for x in L)) [] [0] [1] [0, 1] [-1] [0, -1] [1, -1] [0, 1, -1] [2] [0, 2] [1, 2]
You may also use subsets as an alias for powerset:
sage: subsets([1,2,3]) <generator object ...powerset at 0x...> sage: list(subsets([1,2,3])) [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] The reason we return lists instead of sets is that the elements of sets must be hashable and many structures on which one wants the powerset consist of non-hashable objects.
>>> from sage.all import * >>> subsets([Integer(1),Integer(2),Integer(3)]) <generator object ...powerset at 0x...> >>> list(subsets([Integer(1),Integer(2),Integer(3)])) [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] The reason we return lists instead of sets is that the elements of sets must be hashable and many structures on which one wants the powerset consist of non-hashable objects.
AUTHORS:
William Stein
Nils Bruin (2006-12-19): rewrite to work for not-necessarily finite objects X.
- sage.combinat.subset.uniq(L)[source]#
Iterate over the elements of
L
, yielding every element at most once: keep only the first occurrence of any item.The items must be hashable.
INPUT:
L
– iterable
EXAMPLES:
sage: L = [1, 1, 8, -5, 3, -5, 'a', 'x', 'a'] sage: it = uniq(L); it <generator object uniq at ...> sage: list(it) [1, 8, -5, 3, 'a', 'x']
>>> from sage.all import * >>> L = [Integer(1), Integer(1), Integer(8), -Integer(5), Integer(3), -Integer(5), 'a', 'x', 'a'] >>> it = uniq(L); it <generator object uniq at ...> >>> list(it) [1, 8, -5, 3, 'a', 'x']