Ask Your Question
1

several cartesian products

asked 2013-06-13 23:10:48 -0500

emiliocba gravatar image

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 flag offensive close merge delete

4 answers

Sort by ยป oldest newest most voted
1

answered 2013-06-13 23:37:17 -0500

tmonteil gravatar image

updated 2013-06-13 23:43:54 -0500

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)]))
edit flag offensive delete link more

Comments

Great! Thank you.-.

emiliocba gravatar imageemiliocba ( 2013-06-13 23:54:17 -0500 )edit

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

kcrisman gravatar imagekcrisman ( 2013-06-14 02:56:07 -0500 )edit

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

tmonteil gravatar imagetmonteil ( 2013-06-15 05:02:38 -0500 )edit
2

answered 2013-06-15 23:59:00 -0500

tmonteil gravatar image

updated 2013-06-16 11:35:10 -0500

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]]
edit flag offensive delete link more
1

answered 2013-06-15 22:12:48 -0500

updated 2013-06-15 22:13:27 -0500

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.

edit flag offensive delete link more
0

answered 2013-06-15 05:09:32 -0500

tmonteil gravatar image

updated 2013-06-15 05:12:30 -0500

(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
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-06-13 23:10:48 -0500

Seen: 275 times

Last updated: Jun 16 '13