several cartesian products

savecancel

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

Note that in the answers of tmonteil you do not have the condition $a_1 \leq a_2 \leq \ldots \leq a_m$. To do so, you may use the very flexible IntegerListsLex as in

sage: V = IntegerListsLex(5, floor=lambda x: 1, min_slope=0)
sage: list(V)
[[5], [2, 3], [1, 4], [1, 2, 2], [1, 1, 3], [1, 1, 1, 2], [1, 1, 1, 1, 1]]

the argument floor specifies the lower bound for the element of the list, and the slope is the difference between two consecutive elemtns of the list. In particular, for increasing sequence you may use

sage: V = IntegerListsLex(7, floor=lambda x: 1, min_slope=1)
sage: list(V)
[[7], [3, 4], [2, 5], [1, 6], [1, 2, 4]]

But note that with that solution you need to specify the sum of the elements.

(answer to a previous comment by @kcrisman)

Well, using IntegerVectors is not straightforward since, when we want to use IntegerVectors as a tool to generate vectors, it seems that we need to specify the sum of the components, hence we have to chain all possible sums (from 0 to n*q):

sage: import itertools
sage: multicartvectint = lambda n,q : itertools.chain.from_iterable([IntegerVectors(i,n,max_part=q) for i in range(n*q+1)])

This works as well (the ordering will be different), but seems slower than using cartesian_product_iterator():

sage: timeit('list(multicartvectint(5,5))')                                                                                
5 loops, best of 3: 3.14 s per loop
sage: timeit('list(multicartvect(5,5))')   
5 loops, best of 3: 1.15 s per loop

sage: timeit('list(multicartvectint(6,6))')
5 loops, best of 3: 46.5 s per loop
sage: timeit('list(multicartvect(6,6))')   
5 loops, best of 3: 18.3 s per loop