There are integer vectors of sum with parts:

Here is the list:

You can use the function combinat::integerVectors::first to get the “first” integer vector of a given sum:

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 returns FAIL when the last integer vector is given in the input:

If you want to run through the integer vectors of a given sum, you can generate them one by one to save memory:

Typically, this would be used as follows:

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 :

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 :

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]:

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 :

This is the list of the integer vectors of sum lower bounded by [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:

This is the list of the integer vectors of sum with parts such that two consecutive parts differ by at most one unit:

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 :

Idem with an Outer constraint:

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:

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

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:

A similar trick can be used to generate Dyck words instead. Here is the list of Dyck words of length :

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:

Alltogether, there are 2*4*3=24 ordered -partitions of [1,3,2]:

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).