several cartesian products

Hi,

I want to construct, given $m$ and $q$, the list of all vectors $v=(a_1,\dots,a_m)$ such that $0\leq a_1\leq \dots \leq a_m < q$. I tried to use "CartesianProducts" but I don't known how to iterate it $m$-times.

Thanks.-.

edit retag close merge delete

Sort by » oldest newest most voted

You can create a list of m iterators and then call cartesian_product_iterator() on it:

sage: multicart = lambda m,q : cartesian_product_iterator([xrange(q+1) for i in range(m)])
sage: list(multicart(3,2))
[(0, 0, 0),
(0, 0, 1),
(0, 0, 2),
(0, 1, 0),
(0, 1, 1),
(0, 1, 2),
(0, 2, 0),
(0, 2, 1),
(0, 2, 2),
(1, 0, 0),
(1, 0, 1),
(1, 0, 2),
(1, 1, 0),
(1, 1, 1),
(1, 1, 2),
(1, 2, 0),
(1, 2, 1),
(1, 2, 2),
(2, 0, 0),
(2, 0, 1),
(2, 0, 2),
(2, 1, 0),
(2, 1, 1),
(2, 1, 2),
(2, 2, 0),
(2, 2, 1),
(2, 2, 2)]


You can see this very similar question.

Now, if you want true vectors instead of tuples, you can do:

sage: import itertools
sage: multicartvect = lambda m,q : itertools.imap(vector, cartesian_product_iterator([xrange(q+1) for i in range(m)]))

more

Great! Thank you.-.

( 2013-06-13 23:54:17 -0600 )edit

Thierry, is it possible that using a filter on IntegerVector might work as well?

( 2013-06-14 02:56:07 -0600 )edit

Not enough space, see my answer below (by the way, is it possible to allow more characters in comments ?).

( 2013-06-15 05:02:38 -0600 )edit

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

more

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.

more

(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

more