tuples with +-1

sage-command

asked 2013-07-10 04:55:40 +0100

141 ●6 ●11 ●20

Is there a simple command that for any $n\in \mathbb N$ gives the list of all $n$-tuples with coefficients $\pm1$? Thus, the list has $2^m$ elements. Thanks.-.

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2013-07-10 06:54:34 +0100

vdelecroix
7645 ●20 ●85 ●168 http://www.labri.fr/pe...

updated 2013-07-10 06:59:48 +0100

The fastest is

sage: from itertools import product
sage: for p in product((1,-1), repeat=4): print p
(1, 1, 1, 1)
(1, 1, 1, -1)
...
(-1, -1, -1, -1)

and if you want the list

sage: list(product((1,-1), repeat=4))
[(1, 1, 1, 1), (1, 1, 1, -1), ..., (-1, -1, -1, -1)]

If you care about performances, you can evaluate the timings

sage: timeit('for p in Words(length=8, alphabet=[-1,1]): pass')
25 loops, best of 3: 7.77 ms per loop
sage: timeit('for p in cartesian_product_iterator([[-1,1] for i in range(8)]): pass')
625 loops, best of 3: 868 µs per loop
sage: timeit('for p in product((1,-1), repeat=8): pass')
625 loops, best of 3: 26.6 µs per loop

So product is fastest, then comes cartesian_product_iterator and then words. The difference is non non-negligible!

edit flag offensive delete link

Comments

Nice, comparison. So, it seems we should update `sage/misc/mrange.py` to be based on the more recent `itertools.product`.

tmonteil ( 2013-07-10 08:09:43 +0100 )edit

product in itertools is *older* than Sage!

vdelecroix ( 2013-07-10 08:11:40 +0100 )edit

Definitely not: `itertools.product` [appears in Python `2.6`](http://docs.python.org/2/library/itertools.html#itertools.product) which was [released in October 2008](http://www.python.org/download/releases/2.6/). According to `hg blame -d` and the copyright notice, most of the code (not the doc) of `sage/misc/mrange.py` was [written in July 2006](http://hg.sagemath.org/sage-main/src/tip/sage/misc/mrange.py?at=default), more than two years before !

tmonteil ( 2013-07-10 14:06:13 +0100 )edit

I see. Thank you! I always thought that we do not see evolution of Python inside Sage but I was definitely wrong!

vdelecroix ( 2013-07-10 14:09:41 +0100 )edit

add a comment

answered 2013-07-10 06:09:31 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

updated 2013-07-10 06:19:12 +0100

You can use the words of length $n$ over the alphabet $\{-1,1\}$, and the transform each of them into a tuple:

sage: n = 4
sage: W = Words(length=n, alphabet=[-1,1])
sage: W
Words of length 4 over {-1, 1}
sage: L = [tuple(w) for w in W]               
sage: L
[(-1, -1, -1, -1),
 (-1, -1, -1, 1),
 (-1, -1, 1, -1),
 (-1, -1, 1, 1),
 (-1, 1, -1, -1),
 (-1, 1, -1, 1),
 (-1, 1, 1, -1),
 (-1, 1, 1, 1),
 (1, -1, -1, -1),
 (1, -1, -1, 1),
 (1, -1, 1, -1),
 (1, -1, 1, 1),
 (1, 1, -1, -1),
 (1, 1, -1, 1),
 (1, 1, 1, -1),
 (1, 1, 1, 1)]

If $n$ is large and you want to save memory, you can creat an iterator instead of a list, by writing, instead of L:

sage: It = (tuple(w) for w in W)                
sage: for i in It:              
....:     print i
....:     
(-1, -1, -1, -1)
(-1, -1, -1, 1)
(-1, -1, 1, -1)
(-1, -1, 1, 1)
(-1, 1, -1, -1)
(-1, 1, -1, 1)
(-1, 1, 1, -1)
(-1, 1, 1, 1)
(1, -1, -1, -1)
(1, -1, -1, 1)
(1, -1, 1, -1)
(1, -1, 1, 1)
(1, 1, -1, -1)
(1, 1, -1, 1)
(1, 1, 1, -1)
(1, 1, 1, 1)

You can also use the cartesian products:

sage: A = cartesian_product_iterator([[-1,1] for i in range(n)])
sage: for i in A:
....:     print i
....:     
(-1, -1, -1, -1)
(-1, -1, -1, 1)
(-1, -1, 1, -1)
(-1, -1, 1, 1)
(-1, 1, -1, -1)
(-1, 1, -1, 1)
(-1, 1, 1, -1)
(-1, 1, 1, 1)
(1, -1, -1, -1)
(1, -1, -1, 1)
(1, -1, 1, -1)
(1, -1, 1, 1)
(1, 1, -1, -1)
(1, 1, -1, 1)
(1, 1, 1, -1)
(1, 1, 1, 1)

edit flag offensive delete link

Comments

Nice and simple answers. Thank you!

emiliocba ( 2013-07-10 06:58:20 +0100 )edit

add a comment

Your Answer

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

Add Answer

tuples with +-1

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

tuples with +-1 edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

tuples with +-1