[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

Method generator: generator for subsets

Method list: list of the subsets

Method first: first subset

Method last: last subset

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