[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

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

Method count: number of elements of a cartesian product

Method generator: generator for the elements of a cartesian product

Method list: list of the elements of a cartesian product

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