[Previous] [Next] [Contents]

## `combinat::subsets` -- subsets of a set

#### Introduction

The library `combinat::subsets` provides functions for counting, generating, and manipulating the subsets of a set.

#### Categories

`Cat::CombinatorialClass`

#### Entries

domtype

The MuPAD domain used to represent subsets: `DOM_SET`

#### Method count: number of subsets

- `count(set s)`

- Returns the number of subsets of `s`.

- `count(nonnegative integer n)`

- Returns the number of subsets of 1, 2, ..., n.

- `count(set s, nonnegative integer k)`

- Returns the number of subsets of `s` of size `k`.

- `count(nonnegative integer n, nonnegative integer k)`

- Returns the number of subsets of 1, 2, ..., n of size `k`.

#### Method generator: generator for subsets

- `generator(set s)`

- Returns a generator for the subsets of `s`.

- `generator(nonnegative integer n)`

- Returns a generator for the subsets of 1, 2, ..., n.

- `generator(set s, nonnegative integer k)`

- Returns a generator for the subsets of `s` of size `k`.

- `generator(nonnegative integer n, nonnegative integer k)`

- Returns a generator for the subsets of 1, 2, ..., n of size `k`.

#### Method list: list of the subsets

- `list(set s)`

- Returns the list of the subsets of `s`.

- `list(nonnegative integer n)`

- Returns the list of the subsets of 1, 2, ..., n.

- `list(set s, nonnegative integer k)`

- Returns the list of the subsets of `s` of size `k`.

- `list(nonnegative integer n, nonnegative integer k)`

- Returns the list of the subsets of 1, 2, ..., n of size `k`.

#### Method first: first subset

- `first(set s)`

- Returns the first subset of `s`.

- `first(nonnegative integer n)`

- Returns the first subset of 1, 2, ..., n.

- `first(set s, nonnegative integer k)`

- Returns the first subset of `s` of size `k`, or FAIL if there is none.

- `first(nonnegative integer n, nonnegative integer k)`

- Returns the first subset of 1, 2, ..., n of size `k`, or FAIL if there is none.

#### Method last: last subset

- `last(set s)`

- Returns the last subset of `s`.

- `last(nonnegative integer n)`

- Returns the last subset of 1, 2, ..., n.

- `last(set s, nonnegative integer k)`

- Returns the last subset of `s` of size `k`.

- `last(nonnegative integer n, nonnegative integer k)`

- Returns the last subset of 1, 2, ..., n of size `k`.

#### Example 1

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}

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package