combinat::integerVectors
--
integer vectors
The library combinat::integerVectors
provides functions for counting,
generating, and manipulating integer vectors.
v
of sum n
with k
parts is a list of k
nonnegative integers which sum up to
n
.Cat::IntegerListsLexClass
The MuPAD domain used to represent integer vectors: DOM_LIST
count(nonnegative integer n, nonnegative integer k
<, constraints>)
n
with
k
parts satisfying constraints
.
generator(nonnegative integer n, nonnegative integer k <, constraints>)
n
with k
parts satisfying
constraints
.
list(nonnegative integer n, nonnegative integer k
<, constraints>)
n
with
k
parts satisfying constraints
.
first(nonnegative integer n, nonnegative integer k
<, constraints>)
n
with k
parts satisfying constraints
or FAIL
if there is
none.
Next(integer vector v <, constraints>)
v
satisfying
constraints
or FAIL
if there is none.There are 15 integer vectors of sum 4 with 3 parts:
>> combinat::integerVectors::count(4, 3)
15
Here is the list:
>> combinat::integerVectors::list(4, 3)
[[4, 0, 0], [3, 1, 0], [3, 0, 1], [2, 2, 0], [2, 1, 1], [2, 0, 2], [1, 3, 0], [1, 2, 1], [1, 1, 2], [1, 0, 3], [0, 4, 0], [0, 3, 1], [0, 2, 2], [0, 1, 3], [0, 0, 4]]
You can use the function combinat::integerVectors::first
to get the ``first'' integer vector of a given sum:
>> combinat::integerVectors::first(4, 3)
[4, 0, 0]
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])
[3, 1, 0]
combinat::integerVectors::Next
returns FAIL
when
the last integer vector is given in the input:
>> combinat::integerVectors::Next([0, 0, 4])
FAIL
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();
[2, 0] [1, 1] [0, 2] FAIL
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 4 with all parts at most 2:
>> combinat::integerVectors::list(4, 3, MaxPart=2)
[[2, 2, 0], [2, 1, 1], [2, 0, 2], [1, 2, 1], [1, 1, 2], [0, 2, 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 4 with all parts at least 1:
>> combinat::integerVectors::list(4, 3, MinPart=1)
[[2, 1, 1], [1, 2, 1], [1, 1, 2]]
The options Inner, and Outer can be used to set part-by-part
inclusion constraints. This is the list of the integer vectors
of 4 upper bounded by [3, 1, 2]
:
>> combinat::integerVectors::list(4, 3, Outer=[3, 1, 2])
[[3, 1, 0], [3, 0, 1], [2, 1, 1], [2, 0, 2], [1, 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 4 and of length at most 3 such that the first and third parts are at most 1:
>> combinat::integerVectors::list(4, 3, Outer=[1, infinity, 1])
[[1, 3, 0], [1, 2, 1], [0, 4, 0], [0, 3, 1]]
This is the list of the integer vectors of sum 4 lower bounded by
[1, 1, 1]
:
>> combinat::integerVectors::list(4, 3, Inner=[1, 1, 1])
[[2, 1, 1], [1, 2, 1], [1, 1, 2]]
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 4 with 3 parts:
>> combinat::integerVectors::list(4, 3, MinSlope=0)
[[1, 1, 2], [0, 2, 2], [0, 1, 3], [0, 0, 4]]
This is the list of the integer vectors of sum 4 with 3 parts such that two consecutive parts differ by at most one unit:
>> combinat::integerVectors::list(4, 3, MinSlope=-1, MaxSlope=1)
[[2, 1, 1], [1, 2, 1], [1, 1, 2]]
The constraints can be combined together in all reasonable ways. This is the list of the integer vectors of sum 11 with 3 parts between 2 and 5 such that the difference between two consecutive parts is between -2 and 2:
>> combinat::integerVectors::list(11, 3,
MinSlope=-2, MaxSlope=2,
MinPart=2, MaxPart=5)
[[5, 4, 2], [5, 3, 3], [4, 4, 3], [4, 3, 4], [3, 5, 3], [3, 4, 4], [3, 3, 5], [2, 4, 5]]
Idem with an Outer constraint:
>> combinat::integerVectors::list(11, 3,
MinSlope=-2, MaxSlope=2,
MinPart=2, MaxPart=5,
Outer=[4,5,4])
[[4, 4, 3], [4, 3, 4], [3, 5, 3], [3, 4, 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)
[[3, 0, 2], [2, 1, 2], [2, 0, 3]]
We demonstrate how to generate the monomials in the variables
x,y,z
of total degree 6 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])))
5 4 4 2 3 2 [x z, x y z, x z , x y z ]
We demonstrate how to generate the Motzkin words of a given
length k
. A Motzkin word is a list of -1, 0, and 1 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 N×N starting at (0,0) with right-down,
right and right-up steps, and ending at (n,0). 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, 5,
MinSlope=-1, MaxSlope=1,
Outer=[0, 1, 2, 1, 0]) $ s=0..4),
l -> [l[i+1]-l[i] $ i=1..nops(l)-1])
[[0, 0, 0, 0], [1, -1, 0, 0], [0, 1, -1, 0], [0, 0, 1, -1], [1, 0, -1, 0], [1, -1, 1, -1], [0, 1, 0, -1], [1, 0, 0, -1], [1, 1, -1, -1]]
A similar trick can be used to generate Dyck words instead. Here is the list of Dyck words of length 2×4:
>> 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();
[[1, 3, 2], [0, 0, 0]], [[1, 3, 1], [0, 0, 1]], [[1, 3, 0], [0, 0, 2]], [[1, 2, 2], [0, 1, 0]], [[1, 2, 1], [0, 1, 1]]
Alltogether, there are 2*4*3=24
ordered 2-partitions of
[1,3,2]
:
>> g := orderedIntegerVectorPartitionsGenerator([1,3,2], 2):
combinat::generators::count(g);
24
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
).
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.
Ax::systemRep
MuPAD Combinat, an open source algebraic combinatorics package