![]() | 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]]