Ask Your Question
1

Drawing all paths from (0, 0) to (n, n) moving one unit right or up

asked 2016-04-23 05:16:54 +0100

TARS gravatar image

updated 2016-04-23 13:42:33 +0100

kcrisman gravatar image

This question is just the same as this one 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?

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
0

answered 2016-04-23 21:03:02 +0100

FrédéricC gravatar image

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

answered 2016-04-23 21:11:03 +0100

tmonteil gravatar image

updated 2016-04-23 21:14:03 +0100

Concerning the generation of such paths, Sage has tools to generate lists of nonnegative integers with constraints, see IntegerListsLex?. Here you want a list of 0s and 1s 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/refer...

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

1 follower

Stats

Asked: 2016-04-23 05:08:30 +0100

Seen: 405 times

Last updated: Apr 23 '16