ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 23 Apr 2016 14:11:03 -0500Drawing all paths from (0, 0) to (n, n) moving one unit right or uphttp://ask.sagemath.org/question/33201/drawing-all-paths-from-0-0-to-n-n-moving-one-unit-right-or-up/This question is just the same as [this one](http://mathematica.stackexchange.com/questions/112395/how-to-draw-all-paths-from-1-1-to-n-n-by-move-1-0-or-0-1) made for Mathematica. I saw it and I was trying to reproduce it in Sage just for fun, but it's getting longer than I like and I would love to know your approach in Sage. I think it's a great way to learn. This is half of my try:
n=3
A=sum(line([(j, i), (n, i)]) for j in range(n+1) for i in range(n+1))
B=sum(line([(i, j), (i, n)]) for j in range(n+1) for i in range(n+1))
G = Graphics()
G += A + B
G.show(figsize=[4,4], axes=False)
result = []
combinations = [bin(i)[2:] for i in range(1, int('111111', 2))]
for num in combinations:
valid = ''.join(['0']*(6-len(num))) + num
zeros = valid.count('0')
ones = valid.count('1')
if zeros == 3 and ones == 3:
result.append(str(valid))
#At this point all the paths are stored in the variable 'results' in binary form.
#For example '010101' means right, left, right, left, right, left
paths = [[]]
for element in result:
path = []
for index, direction in enumerate(list(element)):
if direction == '0':
path.append((index, index - 1))
else:
path.append((index - 1, index))
paths.append(path)
At this point the list of list called paths is not well constructed. I realized I would have to put some `if` statements to make it work but I'm losing motivation in my solution because it's getting ugly and I don't think is very efficient.
How would you do it?
Fri, 22 Apr 2016 22:08:30 -0500http://ask.sagemath.org/question/33201/drawing-all-paths-from-0-0-to-n-n-moving-one-unit-right-or-up/Answer by FrédéricC for <p>This question is just the same as <a href="http://mathematica.stackexchange.com/questions/112395/how-to-draw-all-paths-from-1-1-to-n-n-by-move-1-0-or-0-1">this one</a> made for Mathematica. I saw it and I was trying to reproduce it in Sage just for fun, but it's getting longer than I like and I would love to know your approach in Sage. I think it's a great way to learn. This is half of my try:</p>
<pre><code>n=3
A=sum(line([(j, i), (n, i)]) for j in range(n+1) for i in range(n+1))
B=sum(line([(i, j), (i, n)]) for j in range(n+1) for i in range(n+1))
G = Graphics()
G += A + B
G.show(figsize=[4,4], axes=False)
result = []
combinations = [bin(i)[2:] for i in range(1, int('111111', 2))]
for num in combinations:
valid = ''.join(['0']*(6-len(num))) + num
zeros = valid.count('0')
ones = valid.count('1')
if zeros == 3 and ones == 3:
result.append(str(valid))
#At this point all the paths are stored in the variable 'results' in binary form.
#For example '010101' means right, left, right, left, right, left
paths = [[]]
for element in result:
path = []
for index, direction in enumerate(list(element)):
if direction == '0':
path.append((index, index - 1))
else:
path.append((index - 1, index))
paths.append(path)
</code></pre>
<p>At this point the list of list called paths is not well constructed. I realized I would have to put some <code>if</code> statements to make it work but I'm losing motivation in my solution because it's getting ugly and I don't think is very efficient.</p>
<p>How would you do it?</p>
http://ask.sagemath.org/question/33201/drawing-all-paths-from-0-0-to-n-n-moving-one-unit-right-or-up/?answer=33212#post-id-33212Here is a try
def all_paths(n):
W0 = Word([0] * n)
W1 = Word([1] * n)
G = Graphics()
N = QQ(binomial(2 * n, n))
col = rainbow(N)
shift = vector([1/N, -1/N])
right = vector([0, 1])
up = vector([1, 0])
zero = vector([0, 0])
for k, word in enumerate(W0.shuffle(W1)):
path = [right if l else up for l in word]
coords = []
z = zero
for x in path:
z += x
coords.append(z)
G += line2d(coords, color=col[k])
zero += shift
return G
Sat, 23 Apr 2016 14:03:02 -0500http://ask.sagemath.org/question/33201/drawing-all-paths-from-0-0-to-n-n-moving-one-unit-right-or-up/?answer=33212#post-id-33212Answer by tmonteil for <p>This question is just the same as <a href="http://mathematica.stackexchange.com/questions/112395/how-to-draw-all-paths-from-1-1-to-n-n-by-move-1-0-or-0-1">this one</a> made for Mathematica. I saw it and I was trying to reproduce it in Sage just for fun, but it's getting longer than I like and I would love to know your approach in Sage. I think it's a great way to learn. This is half of my try:</p>
<pre><code>n=3
A=sum(line([(j, i), (n, i)]) for j in range(n+1) for i in range(n+1))
B=sum(line([(i, j), (i, n)]) for j in range(n+1) for i in range(n+1))
G = Graphics()
G += A + B
G.show(figsize=[4,4], axes=False)
result = []
combinations = [bin(i)[2:] for i in range(1, int('111111', 2))]
for num in combinations:
valid = ''.join(['0']*(6-len(num))) + num
zeros = valid.count('0')
ones = valid.count('1')
if zeros == 3 and ones == 3:
result.append(str(valid))
#At this point all the paths are stored in the variable 'results' in binary form.
#For example '010101' means right, left, right, left, right, left
paths = [[]]
for element in result:
path = []
for index, direction in enumerate(list(element)):
if direction == '0':
path.append((index, index - 1))
else:
path.append((index - 1, index))
paths.append(path)
</code></pre>
<p>At this point the list of list called paths is not well constructed. I realized I would have to put some <code>if</code> statements to make it work but I'm losing motivation in my solution because it's getting ugly and I don't think is very efficient.</p>
<p>How would you do it?</p>
http://ask.sagemath.org/question/33201/drawing-all-paths-from-0-0-to-n-n-moving-one-unit-right-or-up/?answer=33213#post-id-33213Concerning the generation of such paths, Sage has tools to generate lists of nonnegative integers with constraints, see `IntegerListsLex?`. Here you want a list of `0`s and `1`s of length `2*n` whose sum is `n`. So you can do:
sage: n = 3
sage: IntegerListsLex(length=2*n,n=n,max_part=1)
You can iterate over this by doing:
for L in IntegerListsLex(length=2*n,n=n,max_part=1):
blah
You can transform the generator into a list to check that nothing is missing:
sage: list(IntegerListsLex(length=2*n,n=n,max_part=1))
[[1, 1, 1, 0, 0, 0],
[1, 1, 0, 1, 0, 0],
[1, 1, 0, 0, 1, 0],
[1, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0],
[1, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 1, 0],
[1, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 1, 1],
[0, 1, 1, 1, 0, 0],
[0, 1, 1, 0, 1, 0],
[0, 1, 1, 0, 0, 1],
[0, 1, 0, 1, 1, 0],
[0, 1, 0, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[0, 0, 1, 1, 1, 0],
[0, 0, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 1, 1]]
sage: len(list(IntegerListsLex(length=2*n,n=n,max_part=1)))
20
sage: binomial(2*n,n)
20
Concerning the plotting, if you plot everything on the same plot, you will end up with a grid. I suggest to look towards animations, see http://doc.sagemath.org/html/en/reference/plotting/sage/plot/animate.html
Sat, 23 Apr 2016 14:11:03 -0500http://ask.sagemath.org/question/33201/drawing-all-paths-from-0-0-to-n-n-moving-one-unit-right-or-up/?answer=33213#post-id-33213