Revision history [back]

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

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

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