combinat
The combinat
library provides combinatorial functions, as well as
tools for counting, generating, and manipulating combinatorial
objects.
It consists of a subset of the algebraic combinatorics contribution package MuPAD-Combinat version 1.0. The full featured package, when installed, can be loaded with:
>> package("Combinat")
See http://mupad-combinat.sourceforge.net/ for details.
The library functions are called using the library name
combinat
and the name of the function. E.g., use
>> combinat::bell(5)
to compute the 5-th Bell number. This mechanism avoids naming
conflicts with other library functions.
If this is found to be inconvenient, then the routines of the
combinat
library may be exported via export
. E.g., after calling
>> export(combinat, bell)
the function combinat::bell
may be called directly:
>> bell(5)
All routines of the combinat
library are exported
simultaneously by
>> export(combinat)
The functions and sub-libraries available in the combinat
library can be listed using
>> info(combinat)
The library package contains three different sorts of features: functions for computing classical sequences of numbers, domains called combinatorial classes of classical combinatorial objects including functions for counting and generating and manipulating these objects and finally libraries of handy tools including highly versatile and configurable algorithms for generating various classes of objects.
The most important part of the combinat
library, i.e. the part devoted to combinatorial objects, is
organized in separate domains with similar interfaces, one for each
combinatorial class. For example,
combinat::cartesianProduct::count
is used to determine the number
of elements in a cartesian product, while combinat::subsets::count
returns the number of subsets of a set. The following domains are
provided:
combinat::partitions
provides functions dealing with
partitions, i.e., decreasing lists of natural numbers with a fixed sum.
combinat::skewPartitions
provides functions dealing with skew
partitions, i.e., a pair of two partitions, where the second partition
is a inner partition of the first.
combinat::compositions
deals with compositions of natural
numbers, i.e., with lists of natural numbers with a fixed sum.
combinat::integerMatrices
deals with matrices of nonnegative
integers of fixed sum for rows and columns.
combinat::integerVectors
deals with vectors of nonnegative
integers of fixed length and fixed sum.
combinat::integerVectorsWeighted
is similar, but the sum is
replaced by a weighted sum.
combinat::cartesianProduct
provides functions dealing with the
Cartesian product of a finite number of sets or lists.
combinat::subsets
deals with subsets of a set.
combinat::permutations
works on permutations of lists and also
standard permutations (i.e. permutations of {1,...,n}).
combinat::words
deals with words, i.e., lists of
fixed length consisting of elements of a specified alphabet.
combinat::subwords
deals with subwords: Starting with a given
list, delete any number of entries.
combinat::dyckWords
deals with Dyck words. These can be
interpreted as words of well balanced parentheses.
combinat::tableaux
provides utilities for tableaux. These are
useful for computations on symmetric functions and polynomials, among
other things.
combinat::decomposableObjects
deals with objects that can be
described recursively by a grammar.
combinat::trees
provides functions to generate and manipulate
trees.
combinat::binaryTrees
provides functions to generate and
manipulate binary trees.
combinat::linearExtensions
provides functions to enumerate
linear extensions of partially ordered sets.
Some of the previous combinatorial classes provide further sub-domains, this feature should be extensively extended in the future:
combinat::binaryTrees
:
combinat::binaryTrees::fromSaillance
for enumerating binaryTrees by saillance.
combinat::binaryTrees::shuffle
with
utilities for the shuffle product of two binary trees.
combinat::compositions
:
combinat::compositions::finer
to deal
with compositions finer than a given one;
combinat::compositions::fatter
to deal
with compositions fatter than a given one;
combinat::compositions::finerVectors
to
deal with integer vectors finer than a given composition;
combinat::words
:
combinat::words::fromStandard
to enumerate
words with a given standard permutations;
combinat::words::shuffle
to compute the
shuffle of two words.
To provide default implementations and to ensure that the interfaces are
compatible, all combinatorial domains belong to the category
Cat::CombinatorialClass
. The purpose of this category is to specify
the behavior of several standardized functions. Note that a specific
combinatorial class does not need to implement all these functions. The
category Cat::CombinatorialClass
also provides default implementations
(possibly inefficient) for some of these.
Here are the list and the meanings of these standard functions:
isA(
|
is an object an element of the class (of size size ) |
size(
|
size of the object object |
count( <size>)
|
number of objects (of size size ) |
generatingSeries(s, <ident>)
| generating series by size |
generator( <size>)
|
generator for all the objects (of size size ) |
list( <size>)
|
list of all the objects (of size size ) |
first( <size>)
|
first object (of size size ) or FAIL |
last( <size>)
|
last object (of size size ) or FAIL |
Next(s)
|
next object after s or FAIL |
previous(s)
|
previous object before s or FAIL |
rank(s)
|
rank of the object s |
unrank(r <, size>)
|
r -th object (of size size ), or FAIL |
random( <size>)
|
random object (of size size ) or FAIL |
_less(s1, s2)
|
comparison of the objects s1 and s2
|
Next
is capitalized because next
is a reserved
keyword in MuPAD.
Note also that, in most packages, these functions take some other
optional arguments. In this case, the functions isA
,
count
, list
, and generator
accept the same
arguments.
For most combinatorial classes cl
, the call
cl(
is a shortcut for size
)cl::list(
;
exceptions to this rule include, e.g. size
)combinat::partitions
;
this feature is solely provided as a syntactic sugar for interactive
use; please do not use it in programs!
In a near future, we plan to add functions to manipulate combinatorial classes, for example to construct subclasses of a given class. So it is very important to stick closely to these conventions.
The following methods are implemented in more than one of those libraries:
count |
generator |
list |
first |
last |
Next |
previous |
rank |
unrank |
random | |
partitions | + | + | + | + | - | + | - | - | - | - |
skewPartitions | + | + | + | - | - | - | - | - | - | - |
compositions | + | + | + | + | - | + | - | - | - | - |
integerMatrices | + | + | + | - | - | - | - | - | - | - |
integerVectors | + | + | + | + | - | + | - | - | - | - |
integerVectors Weighted
| + | + | + | + | - | + | - | - | - | - |
integerLists LexTools
| - | + | + | + | - | + | - | - | - | - |
cartesianProduct | + | + | + | - | - | - | - | - | - | - |
subsets | + | + | + | + | + | - | - | - | - | - |
permutations | + | + | + | + | + | + | + | - | - | + |
words | + | + | + | - | - | - | - | - | - | - |
subwords | + | + | + | + | + | - | - | - | - | - |
dyckWords | + | + | + | - | - | - | - | - | - | - |
nonCrossing Partitions
| - | - | - | - | - | - | - | - | - | - |
tableaux | + | + | + | - | - | - | - | - | - | - |
decomposable Objects
| + | + | + | - | - | - | - | - | + | + |
trees
| + | + | + | - | - | - | - | - | + | + |
binaryTrees
| + | + | + | - | - | - | - | - | + | + |
Many of the sub-libraries provide further methods, such as
combinat::permutations::inverse
. See
the corresponding documentation for details.
The combinat
library also contains the following support
sub-libraries, which are used intensively by the previous ones.
combinat::generators
provides utilities for creating and
manipulating generators, i.e., functions which, on each call,
return the next element of a (possibly infinite) sequence of
values.
combinat::integerListsLexTools
provides an algorithm for
generating, in lexicographic order, lists of natural numbers
satisfying certain constraints.
Finally some classical combinatorial sequences of numbers are provided:
combinat::bell
: Bell numbers;
combinat::catalan
: Catalan numbers;
combinat::stirling1
: Stirling numbers of the first kind;
combinat::stirling2
: Stirling numbers of the second kind;
combinat::modStirling
: Modified Stirling numbers;
The combinat
library is articulated around three main categories:
Cat::CombinatorialClass
, which is the basic category for
combinatorial objects. It provides basic functions for types
isA
,
testtype
count
,
generator
list
Cat::DecomposableClass
is used as a front-end category for
combinatorial classes based on the domain
combinat::decomposableObjects
, and is devoted to objects that can be
described by some recursive grammar. This category is a subcategory of
Cat::CombinatorialClass
, and it provides also by default these two
more functions:
unrank
,
random
Cat::IntegerListsLexClass
is used as a front-end category for
combinatorial classes based on combinat::integerListsLexTools
, and
is devoted to lexicographic enumerations of list of integers with a fixed
sum and some prescribed constraints. It is a subcategory of
Cat::CombinatorialClass
and provide also by default the functions:
first
,
Next
,
_less
Most of the libraries are in one of those categories (except combinat::generators
and famous numbers: Bell, Catalan, Stirling, ...).
Here is a classification:
Cat::CombinatorialClass
combinat::binaryTrees::fromSaillance
combinat::binaryTrees::shuffle
combinat::cartesianProduct
combinat::compositions::finer
combinat::compositions::fatter
combinat::compositions::finerVectors
combinat::integerListsLexTools
combinat::integerMatrices
combinat::integerVectorsWeighted
combinat::linearExtensions
combinat::nonCrossingPartitions
combinat::permutations
combinat::skewPartitions
combinat::subsets
combinat::subwords
combinat::tableaux
combinat::words
combinat::words::fromStandard
combinat::words::shuffle
Cat::DecomposableClass
Cat::IntegerListsLexClass
In this section, we pick a few sample applications at random.
First, we export the combinat
library
to save us some typing:
>> export(combinat):
Note that the sub-libraries such as combinat::partitions
are not intended to be exported.
In our first examples, we use the abbreviated calls for list
generation. We generate the Cartesian product of three lists, we
compute all permutations of the numbers 1, 2, 3, and we ask for
all sub-words of the word [a, b, c, d]
:
>> cartesianProduct([1,2,3],[a,b],[i,ii,iii])
[[1, a, i], [1, a, ii], [1, a, iii], [1, b, i], [1, b, ii], [1, b, iii], [2, a, i], [2, a, ii], [2, a, iii], [2, b, i], [2, b, ii], [2, b, iii], [3, a, i], [3, a, ii], [3, a, iii], [3, b, i], [3, b, ii], [3, b, iii]]
>> permutations(3)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>> subwords([a,b,c,d])
[[], [a], [b], [c], [d], [a, b], [a, c], [a, d], [b, c], [b, d], [c, d], [a, b, c], [a, b, d], [a, c, d], [b, c, d], [a, b, c, d]]
Dyck words, as stated above, can be interpreted as balanced sequences of parentheses:
>> map(dyckWords(4), dyckWords::toString)
["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"]
MuPAD Combinat, an open source algebraic combinatorics package