ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 16 Jun 2013 06:59:00 +0200several cartesian productshttps://ask.sagemath.org/question/10238/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.-.Fri, 14 Jun 2013 06:10:48 +0200https://ask.sagemath.org/question/10238/several-cartesian-products/Answer by tmonteil for <p>Hi,</p>
<p>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.</p>
<p>Thanks.-.</p>
https://ask.sagemath.org/question/10238/several-cartesian-products/?answer=15088#post-id-15088(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
Sat, 15 Jun 2013 12:09:32 +0200https://ask.sagemath.org/question/10238/several-cartesian-products/?answer=15088#post-id-15088Answer by tmonteil for <p>Hi,</p>
<p>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.</p>
<p>Thanks.-.</p>
https://ask.sagemath.org/question/10238/several-cartesian-products/?answer=15093#post-id-15093Thanks 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]]
Sun, 16 Jun 2013 06:59:00 +0200https://ask.sagemath.org/question/10238/several-cartesian-products/?answer=15093#post-id-15093Answer by vdelecroix for <p>Hi,</p>
<p>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.</p>
<p>Thanks.-.</p>
https://ask.sagemath.org/question/10238/several-cartesian-products/?answer=15092#post-id-15092Note 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.Sun, 16 Jun 2013 05:12:48 +0200https://ask.sagemath.org/question/10238/several-cartesian-products/?answer=15092#post-id-15092Answer by tmonteil for <p>Hi,</p>
<p>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.</p>
<p>Thanks.-.</p>
https://ask.sagemath.org/question/10238/several-cartesian-products/?answer=15083#post-id-15083You 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](http://ask.sagemath.org/question/2688/generating-permutations-of-coefficients).
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)]))
Fri, 14 Jun 2013 06:37:17 +0200https://ask.sagemath.org/question/10238/several-cartesian-products/?answer=15083#post-id-15083Comment by tmonteil for <p>You can create a list of <code>m</code> iterators and then call <code>cartesian_product_iterator()</code> on it:</p>
<pre><code>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)]
</code></pre>
<p>You can see this <a href="http://ask.sagemath.org/question/2688/generating-permutations-of-coefficients">very similar question</a>.</p>
<p>Now, if you want true vectors instead of tuples, you can do:</p>
<pre><code>sage: import itertools
sage: multicartvect = lambda m,q : itertools.imap(vector, cartesian_product_iterator([xrange(q+1) for i in range(m)]))
</code></pre>
https://ask.sagemath.org/question/10238/several-cartesian-products/?comment=17497#post-id-17497Not enough space, see my answer below (by the way, is it possible to allow more characters in comments ?).Sat, 15 Jun 2013 12:02:38 +0200https://ask.sagemath.org/question/10238/several-cartesian-products/?comment=17497#post-id-17497Comment by kcrisman for <p>You can create a list of <code>m</code> iterators and then call <code>cartesian_product_iterator()</code> on it:</p>
<pre><code>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)]
</code></pre>
<p>You can see this <a href="http://ask.sagemath.org/question/2688/generating-permutations-of-coefficients">very similar question</a>.</p>
<p>Now, if you want true vectors instead of tuples, you can do:</p>
<pre><code>sage: import itertools
sage: multicartvect = lambda m,q : itertools.imap(vector, cartesian_product_iterator([xrange(q+1) for i in range(m)]))
</code></pre>
https://ask.sagemath.org/question/10238/several-cartesian-products/?comment=17501#post-id-17501Thierry, is it possible that using a filter on `IntegerVector` might work as well?Fri, 14 Jun 2013 09:56:07 +0200https://ask.sagemath.org/question/10238/several-cartesian-products/?comment=17501#post-id-17501Comment by emiliocba for <p>You can create a list of <code>m</code> iterators and then call <code>cartesian_product_iterator()</code> on it:</p>
<pre><code>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)]
</code></pre>
<p>You can see this <a href="http://ask.sagemath.org/question/2688/generating-permutations-of-coefficients">very similar question</a>.</p>
<p>Now, if you want true vectors instead of tuples, you can do:</p>
<pre><code>sage: import itertools
sage: multicartvect = lambda m,q : itertools.imap(vector, cartesian_product_iterator([xrange(q+1) for i in range(m)]))
</code></pre>
https://ask.sagemath.org/question/10238/several-cartesian-products/?comment=17502#post-id-17502Great! Thank you.-.Fri, 14 Jun 2013 06:54:17 +0200https://ask.sagemath.org/question/10238/several-cartesian-products/?comment=17502#post-id-17502