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)

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]
cardinality()

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
generating_serie(variable='x')

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
random_element()

Return a random element of self with uniform law

EXAMPLES:

sage: S = Subsets([1,1,2,3], submultiset=True)
sage: S.random_element()
[2]
class sage.combinat.subset.SubMultiset_sk(s, k)

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]]
cardinality()

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
generating_serie(variable='x')

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
random_element()

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}
sage.combinat.subset.Subsets(s, k=None, submultiset=False)

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 \(n\) which encode the set \(\{1,2,\dots,n\}\) (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}, {}}, {{}}}
class sage.combinat.subset.Subsets_s(s)

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}}}
an_element()

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}
cardinality()

Returns 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
element_class

alias of Set_object_enumerated

first()

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()
{}
last()

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}
random_element()

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
rank(sub)

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}
underlying_set()

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}
unrank(r)

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
class sage.combinat.subset.Subsets_sk(s, k)

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
an_element()

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}
cardinality()

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
first()

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
last()

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
random_element()

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
rank(sub)

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}
unrank(r)

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
sage.combinat.subset.dict_to_list(d)

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']
sage.combinat.subset.list_to_dict(l)

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}

Previous topic

Similarity class types of matrices with entries in a finite field

Next topic

Subsets whose elements satisfy a predicate pairwise

This Page