[Previous] [Next] [Contents]

## `combinat::cartesianProduct` -- cartesian products

#### Introduction

The library `combinat::cartesianProduct` provides functions for counting and generating elements of cartesian products of sets.

#### Details

- Let s1, s2, ..., sk be k sets. The cartesian product s1 x s2 x ... x sk of s1,s2,...,sk is the set of all k-tuples [x1,x2,...,xk] with xi in si for each i, 1<=i<=k.

- Each set si can be represented either by a set (`DOM_SET`), a list (`DOM_LIST`), or an integer (which represents the set 1,2,...,n).

#### Categories

`Cat::CombinatorialClass`

#### Entries

domtype

The MuPAD domain used to represent cartesian products: `DOM_LIST`

#### Method isA: test if an object is a cartesian product

- `isA(any type cp <, set or list or nonnegative integer s1, ..., set or list or nonnegative integer sk>)`

- Returns whether the object `cp` is an element of a cartesian product.
- If optional arguments are present, returns whether `cp` is a an element of the cartesian product of `s1`, ..., `sk`.

#### Method count: number of elements of a cartesian product

- `count( <set s1> <, set s2> <, ..., set sk>)`

- Returns the number of elements of the cartesian product s1 x s2 x ... x sk.

#### Method generator: generator for the elements of a cartesian product

- `generator( <set s1> <, set s2> <, ..., set sk>)`

- Returns a generator for the elements of the cartesian product s1 x s2 x ... x sk.

#### Method list: list of the elements of a cartesian product

- `list( <set s1> <, set s2> <, ..., set sk>)`

- Returns the list of the elements of the cartesian product s1 x s2 x ... x sk.

#### Example 1

In this example we show how to check whether we have an element of a cartesian product of some sets. The sets can be represented either by a list, a set or a non negative integer.

    >> combinat::cartesianProduct::isA([2, 3, 4], {1, 2}, [a, 3], 7);
       combinat::cartesianProduct::isA([2, 3, 4, d], 2, 3, 4, {a, d});
       combinat::cartesianProduct::isA([2, 3, 4, d], 2, 1, 4, {a, d});
       combinat::cartesianProduct::isA([2, 3, 4, d], 2, 3);

                                       TRUE

                                       TRUE

                                       FALSE

                                       FALSE

If no optional argument is provided (i.e. the sets), the function tests whether an object makes sense as an element of a cartesian product.

    >> combinat::cartesianProduct::isA([2, 3, 4, d]);
       combinat::cartesianProduct::isA([ ]);
       combinat::cartesianProduct::isA(a);

                                       TRUE

                                       TRUE

                                       FALSE

#### Example 2

There are 12 elements in the cartesian product of the sets `{1,2,3}` and `{a,b,c,d}`:

    >> combinat::cartesianProduct::count({1,2,3},{a,b,c,d});

                                        12

Here is the list:

    >> combinat::cartesianProduct::list({1,2,3},{a,b,c,d});

          [[1, a], [1, b], [1, c], [1, d], [2, a], [2, b], [2, c],

             [2, d], [3, a], [3, b], [3, c], [3, d]]

When you want to run through the elements of a cartesian product you can generate them one by one to save memory:

    >> g := combinat::cartesianProduct::generator({1,2},{a,b}):
       g(); g(); g(); g(); g()

                                      [1, a]

                                      [1, b]

                                      [2, a]

                                      [2, b]

                                       FAIL

Typically, this would be used as follows:

    >> g := combinat::cartesianProduct::generator({1,2},{a,b}):
       while (p := g()) <> FAIL do print(p): end:

                                      [1, a]

                                      [1, b]

                                      [2, a]

                                      [2, b]

#### Example 3

Each input set can be represented by a set, a list, or a number:

    >> combinat::cartesianProduct::list({a,b},[x,y],2);

          [[a, x, 1], [a, x, 2], [a, y, 1], [a, y, 2], [b, x, 1],

             [b, x, 2], [b, y, 1], [b, y, 2]]

The empty cartesian product has one element:

    >> combinat::cartesianProduct::list();

                                       [[]]

When any one of the sets is empty, the cartesian product is also empty:

    >> combinat::cartesianProduct::list(2,0);

                                        []

The cartesian product is not commutative:

    >> combinat::cartesianProduct::list({Diamondsuit},2);
       combinat::cartesianProduct::list(2,{Diamondsuit})

                       [[Diamondsuit, 1], [Diamondsuit, 2]]

                       [[1, Diamondsuit], [2, Diamondsuit]]

#### Example 4

Which cards exist, if you have the following suits and numbers available?

    >> combinat::cartesianProduct::list(
                 {Diamondsuit,Heartsuit,Spadesuit,Clubsuit},
                 {7,8,9,10})

          [[Diamondsuit, 7], [Diamondsuit, 8], [Diamondsuit, 9],

             [Diamondsuit, 10], [Heartsuit, 7], [Heartsuit, 8],

             [Heartsuit, 9], [Heartsuit, 10], [Spadesuit, 7],

             [Spadesuit, 8], [Spadesuit, 9], [Spadesuit, 10],

             [Clubsuit, 7], [Clubsuit, 8], [Clubsuit, 9], [Clubsuit, 10]]

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package