1 | initial version |

Wow, thanks to @vdelecroix, i realize that i answered the question about iterating cartesian product and provide all vectors $v=(a_1, \dots, a_m)$ with such that $0 \leq a_i < q$, but not the first question with the condition $0\leq a_1\leq \dots \leq a_m < q$.

Of course, we can filter the previous results and throw the vectors not satisfying the additional condition, but a lot of computation will be done for nothing (especially when `m`

increases). But we can be faster by noticing that a non-decreasing sequence is the integral (partial sums) of a non-negative sequence. Hence, the non-negative (m+1)-tuples that sum to q are in one-to-one correspondence with the non-decreasing m-tuples whose last element is less or equal than `q`

(in one direction, do the partial sum, in the other direction, do the first differences). So, we got a link with the `IntegerVectors`

suggested by @kcrisman:

```
def integrate_but_last(L):
LL = []
s = 0
for i in L[:-1]:
s += i
LL.append(s)
return LL
multicartnondecreasing = lambda m,q : (integrate_but_last(L) for L in IntegerVectors(q-1,m+1))
sage: list(multicartnondecreasing(4,3))
[[2, 2, 2, 2],
[1, 2, 2, 2],
[1, 1, 2, 2],
[1, 1, 1, 2],
[1, 1, 1, 1],
[0, 2, 2, 2],
[0, 1, 2, 2],
[0, 1, 1, 2],
[0, 1, 1, 1],
[0, 0, 2, 2],
[0, 0, 1, 2],
[0, 0, 1, 1],
[0, 0, 0, 2],
[0, 0, 0, 1],
[0, 0, 0, 0]]
```

2 | No.2 Revision |

Wow, thanks to @vdelecroix, i realize that i answered the question about iterating cartesian product and provide all vectors $v=(a_1, \dots, a_m)$ with such that $0 \leq a_i < q$, but not the first question with the condition $0\leq a_1\leq \dots \leq a_m < q$.

Of course, we can filter the previous results and throw away the vectors not satisfying the additional condition, but a lot of computation will be done for nothing (especially when `m`

increases). But we can be faster by noticing that a non-decreasing sequence is the integral (partial sums) of a non-negative sequence. Hence, the non-negative (m+1)-tuples that sum to q are in one-to-one correspondence with the non-decreasing m-tuples whose last element is less or equal than `q`

(in one direction, do the partial sum, in the other direction, do the first differences). So, we got a link with the `IntegerVectors`

suggested by @kcrisman:

```
def integrate_but_last(L):
LL = []
s = 0
for i in L[:-1]:
s += i
LL.append(s)
return LL
multicartnondecreasing = lambda m,q : (integrate_but_last(L) for L in IntegerVectors(q-1,m+1))
sage: list(multicartnondecreasing(4,3))
[[2, 2, 2, 2],
[1, 2, 2, 2],
[1, 1, 2, 2],
[1, 1, 1, 2],
[1, 1, 1, 1],
[0, 2, 2, 2],
[0, 1, 2, 2],
[0, 1, 1, 2],
[0, 1, 1, 1],
[0, 0, 2, 2],
[0, 0, 1, 2],
[0, 0, 1, 1],
[0, 0, 0, 2],
[0, 0, 0, 1],
[0, 0, 0, 0]]
```

3 | No.3 Revision |

~~Wow, thanks ~~Thanks to @vdelecroix, i realize that i answered the question about iterating cartesian product and provide all vectors $v=(a_1, \dots, a_m)$ with such that $0 \leq a_i < q$, but not the first question with the condition $0\leq a_1\leq \dots \leq a_m < q$.

Of course, we can filter the previous results and throw away the vectors not satisfying the additional condition, but a lot of computation will be done for nothing (especially when `m`

increases). But we can be faster by noticing that a non-decreasing sequence is the integral (partial sums) of a non-negative sequence. Hence, the non-negative (m+1)-tuples that sum to q are in one-to-one correspondence with the non-decreasing m-tuples whose last element is less or equal than `q`

(in one direction, do the partial sum, in the other direction, do the first differences). So, we got a link with the `IntegerVectors`

suggested by @kcrisman:

```
def integrate_but_last(L):
LL = []
s = 0
for i in L[:-1]:
s += i
LL.append(s)
return LL
multicartnondecreasing = lambda m,q : (integrate_but_last(L) for L in IntegerVectors(q-1,m+1))
sage: list(multicartnondecreasing(4,3))
[[2, 2, 2, 2],
[1, 2, 2, 2],
[1, 1, 2, 2],
[1, 1, 1, 2],
[1, 1, 1, 1],
[0, 2, 2, 2],
[0, 1, 2, 2],
[0, 1, 1, 2],
[0, 1, 1, 1],
[0, 0, 2, 2],
[0, 0, 1, 2],
[0, 0, 1, 1],
[0, 0, 0, 2],
[0, 0, 0, 1],
[0, 0, 0, 0]]
```

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.