combinat::integerVectors – integer vectors
The library combinat::integerVectors provides functions for counting, generating, and manipulating integer vectors.
Superdomain
Categories
Axioms
Related Domains:
Details:
An integer vector v of sum n with k parts is a list of k nonnegative integers which sum up to n.
All functions for counting and generating accept the following optional constraints on the integer vectors: MinLength, MaxLength, Length, MinPart, MaxPart, Inner, Outer, MinSlope, and MaxSlope. Cf. examples 2, 3, 4, and 5.
Entries
"domtype" |
The MuPAD domain used to represent integer vectors: DOM_LIST |
count – number of integer vectors
combinat::integerVectors::count(nonnegative integer n, nonnegative integer , <constraints>)
Returns the number of integer vectors of sum n with k parts satisfying constraints.
generator – generator for integer vectors
combinat::integerVectors::generator(nonnegative integer n, nonnegative integer , <constraints>)
Returns a generator for the integer vectors of sum n with k parts satisfying constraints.
list – list of the integer vectors
combinat::integerVectors::list(nonnegative integer n, nonnegative integer , <constraints>)
Returns the list of the integer vectors of sum n with k parts satisfying constraints.
first – first integer vector
combinat::integerVectors::first(nonnegative integer n, nonnegative integer , <constraints>)
Returns the first integer vector of sum n with k parts satisfying constraints or FAIL if there is none.
Next – next integer vector
combinat::integerVectors::Next(integer vector , <constraints>)
Returns the integer vector following v satisfying constraints or FAIL if there is none.
There are integer vectors of sum with parts:
combinat::integerVectors::count(4, 3)
Here is the list:
combinat::integerVectors::list(4, 3)
You can use the function combinat::integerVectors::first to get the “first” integer vector of a given sum:
combinat::integerVectors::first(4, 3)
Using combinat::integerVectors::Next, you can calculate the “next” integer vector. This function takes as argument the integer vector relative to which you want the next one:
combinat::integerVectors::Next([4, 0, 0])
combinat::integerVectors::Next returns FAIL when the last integer vector is given in the input:
combinat::integerVectors::Next([0, 0, 4])
If you want to run through the integer vectors of a given sum, you can generate them one by one to save memory:
g := combinat::integerVectors::generator(2, 2):
g(); g(); g(); g();
Typically, this would be used as follows:
g := combinat::integerVectors::generator(2, 2):
while (p := g()) <> FAIL do print(p): end:
[2, 0]
[1, 1]
[0, 2]
The options MinPart and MaxPart can be used to set constraints on the sizes of all parts. Using MaxPart, you can select integer vectors having only small entries. This is the list of the integer vectors of sum with all parts at most :
combinat::integerVectors::list(4, 3, MaxPart=2)
MinPart is complementary to MaxPart and selects integer vectors having only large parts (it takes a non-negative value). This is the list of the integer vectors of sum with all parts at least :
combinat::integerVectors::list(4, 3, MinPart=1)
The options Inner, and Outer can be used to set part-by-part inclusion constraints. This is the list of the integer vectors of upper bounded by [3, 1, 2]:
combinat::integerVectors::list(4, 3, Outer=[3, 1, 2])
Outer sets MaxLength to the length of its argument. Moreover, the parts of Outer may be infinite to clear the constraint on specific parts. This is the list of the integer vectors of sum and of length at most such that the first and third parts are at most :
combinat::integerVectors::list(4, 3, Outer=[1, infinity, 1])
This is the list of the integer vectors of sum lower bounded by [1, 1, 1]:
combinat::integerVectors::list(4, 3, Inner=[1, 1, 1])
The options MinSlope and MaxSlope can be used to set constraints on the slope, that is on the difference p[i+1]-p[i] of two consecutive parts. This is the list of the increasing integer vectors of sum with parts:
combinat::integerVectors::list(4, 3, MinSlope=0)
This is the list of the integer vectors of sum with parts such that two consecutive parts differ by at most one unit:
combinat::integerVectors::list(4, 3, MinSlope=-1, MaxSlope=1)
The constraints can be combined together in all reasonable ways. This is the list of the integer vectors of sum with parts between and such that the difference between two consecutive parts is between and :
combinat::integerVectors::list(11, 3,
MinSlope=-2, MaxSlope=2,
MinPart=2, MaxPart=5)
Idem with an Outer constraint:
combinat::integerVectors::list(11, 3,
MinSlope=-2, MaxSlope=2,
MinPart=2, MaxPart=5,
Outer=[4,5,4])
However, to provide incoherent constraints may yield to strange results. It is up to the user to ensure that the Inner and Outer integer vectors themselves satisfy the parts and slope constraints:
combinat::integerVectors::list(5, 3, Inner=[2, 0, 2], MinPart=2)
We demonstrate how to generate the monomials in the variables x,y,z of total degree which are divisible by x^2z and divide x^5yz^2
map(combinat::integerVectors::list(6, 3, Inner=[2,0,1],
Outer=[5,1,2]), v -> expr(poly([[1,v]], [x,y,z])))
We demonstrate how to generate the Motzkin words of a given length k. A Motzkin word is a list of , , and of length n such that all partial sums are nonnegative and the total sum is zero. Geometrically, this is a discrete path in the integer plane starting at with right-down, right and right-up steps, and ending at . We work on the list of the k+1 partial sums, and use the option Outer to force the first and last one to be zero. Note that Outer itself is required to satisfy the slope constraints. We also disregard the sum s of the partial sums. Here is the list of the Motzkin words of length 5:
map(_concat(combinat::integerVectors::list(s, 6,
MinSlope=-1, MaxSlope=1,
Outer=[0, 1, 2, 2, 1, 0]) $ s=0..7),
l -> [l[i+1]-l[i] $ i=1..nops(l)-1])
A similar trick can be used to generate Dyck words instead. Here is the list of Dyck words of length :
map(_concat(combinat::integerVectors::list(s, 9,
MinSlope=0, MaxSlope=1,
Inner=[0, 1, 1, 2, 2, 3, 3, 4, 4],
Outer=[0, 1, 2, 3, 4, 4, 4, 4, 4]
) $ s=20..26),
l -> combinat::dyckWords::toString
([if l[i+1]=l[i] then 0 else 1 end_if $ i=1..nops(l)-1]))
We show here how to generate the ordered k-partitions of an integer vector m; that is the lists of k integer vectors m1,...,mk such that m1+...+mk=m; or the k x nops(m) matrix with prescribed column sums given by m.
We can build for each part m[i] of m a generator for the integer vectors of sum m[i] with k parts, and take the cartesian product of those generators. Note that this yields lists of l lists of k integers instead of lists of k lists of l integers, so we need to further transpose the lists.
Let's take an example, with m:=[1,3,2] and k:=2. The first part yields the lists [1,0] or [0,1], the second [3,0], [2,1], [1,2], or [0,3] and the last part yields [2,0], [1,1], [0,2]. The first element of the cartesian product is [[1,0], [3,0],[2,0]], and after transposition we get [[1,3,2],[0,0,0]].
Now, here is the code:
orderedIntegerVectorPartitionsGenerator :=
proc(m: combinat::integerVectors, k: Type::PosInt)
option escape;
begin
combinat::generators::map
(// The cartesian product of the generators of integer vectors
combinat::generators::cartesian
(combinat::integerVectors::generator(m[i], k) $ i=1..nops(m)),
// A function that does the transposition
l->[[l[j][i] $ j=1..nops(m)] $ i=1..k]);
end_proc:
g := orderedIntegerVectorPartitionsGenerator([1,3,2], 2):
g(), g(), g(), g(), g();
Alltogether, there are 2*4*3=24 ordered -partitions of [1,3,2]:
g := orderedIntegerVectorPartitionsGenerator([1,3,2], 2):
combinat::generators::count(g);
As an application, this can be used to generate the ordered k-partitions of a multiset s; that is the lists of k multisets s1,...,sk whose union is s; for example, [{a,b,b,b,c}, {a,b,d}] and [{a,b,d}, {a,b,b,b,c}] are two distinct partitions of the multiset {a,a,b,b,b,b,c,d}.
Indeed, a multiset s such as {a,a,b,b,b,b,c,d} can be represented by the integer vector m of its repetitions, here [2,4,1,1]. Now, partitioning s in k multisets is equivalent to finding k integer vectors m1,...,mk that sum up to m as above. We leave as an exercise for the reader to build the appropriate conversion routines and to derive a generator for ordered multiset partitions (hint: use combinat::generators::map).
Background:
Integer vectors are naturally ordered lexicographically. The functions for counting and generating are directly inherited from Cat::IntegerListsLexClass with Length=k. The complexity of the generation algorithm is constant time amortized for each integer vector generated.
Except for the trivial cases, counting is done by brute force generation.