combinat::subsets
--
subsets of a set
The library combinat::subsets
provides functions for counting,
generating, and manipulating the subsets of a set.
Cat::CombinatorialClass
The MuPAD domain used to represent subsets:
DOM_SET
count(set s)
s
.count(nonnegative integer n)
count(set s, nonnegative integer k)
s
of size k
.count(nonnegative integer n, nonnegative integer k)
k
.
generator(set s)
s
.generator(nonnegative integer n)
generator(set s, nonnegative integer k)
s
of size k
.generator(nonnegative integer n, nonnegative integer k)
k
.
list(set s)
s
.list(nonnegative integer n)
list(set s, nonnegative integer k)
s
of size k
.list(nonnegative integer n, nonnegative integer k)
k
.
first(set s)
s
.first(nonnegative integer n)
first(set s, nonnegative integer k)
s
of size k
, or FAIL
if there is none.first(nonnegative integer n, nonnegative integer k)
k
, or FAIL if there is none.
last(set s)
s
.last(nonnegative integer n)
last(set s, nonnegative integer k)
s
of size k
.last(nonnegative integer n, nonnegative integer k)
k
.There are 8 subsets of 1,2,3
:
>> combinat::subsets::count(3);
combinat::subsets::count({1,2,3})
8 8
There are 15 subsets of size 2 in a set of size 6:
>> combinat::subsets::count(6,2);
combinat::subsets::count({a,b,c,d,e,f},2)
15 15
Here is the list of the subsets of a,b,c,d,e
of size 3:
>> combinat::subsets::list({a,b,c,d,e}, 3)
[{a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}]
You can use the functions combinat::subsets::first
and
combinat::subsets::last
to get the ``first'' and ``last''
subset of a set:
>> combinat::subsets::first(4);
combinat::subsets::first({1,2,3,4});
combinat::subsets::first(4,2);
combinat::subsets::first({1,2,3,4},2);
combinat::subsets::last(4);
combinat::subsets::last({1,2,3,4});
combinat::subsets::last(4,2);
combinat::subsets::last({1,2,3,4},2);
{} {} {1, 2} {1, 2} {1, 2, 3, 4} {1, 2, 3, 4} {3, 4} {3, 4}
The specified size for the subsets can exceed the size of the set itself:
>> combinat::subsets::count({1,2,3}, 4);
combinat::subsets::list({1,2,3}, 4);
combinat::subsets::first({1,2,3}, 4);
0 [] FAIL
When you want to run through the subsets of a set, you can generate them one by one to save memory:
>> g := combinat::subsets::generator(3):
g(); g(); g(); g(); g(); g()
{} {1} {2} {3} {1, 2} {1, 3}
Typically, this would be used as follows:
>> g := combinat::subsets::generator(4,2):
while (p := g()) <> FAIL do print(p): end:
{1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4}
Ax::systemRep
MuPAD Combinat, an open source algebraic combinatorics package