Conversation

Is there an easy algorithm to a) count the number of equivalent shortest paths on a manhattan grid b) enumerate them systematically? I wrote a dumb random algo and I could run it for a long time to count unique paths but I imagine there's a closed-form solution?
Image
7
9
Replying to and
By S(a,b), denote the number of shortest paths from (0,0) to (a,b), for a,b >= 0. S(x,0) = S(0,y) = 1. If x,y > 0 , S(x,y) = S(x-1,y) + S(x,y-1). So, looking at an actual grid, you can fill in # of paths through each point, iterating really quickly.
1
2
Replying to and
So, If you're travelling from bottom-left to top-right, first write a 1 in each leftmost and bottommost intersection, then for each empty cell, fill in the sum of the cell to the left and the cell below. Iterate all the way to the top.
1
1
Replying to and
To know how many paths go through a particular point, do the same thing for paths end-point to start-point. The number of full paths going through a particular point is the number of shortest paths from the start to that point, and from the end to that point.
1
1
Replying to
That just gives me the number of paths to (n,m) though, doesn't it? Which can be directly computed as (n+m)!/n!m!... it doesn't give me a way to actually generate all the unique paths
1
Replying to
Oh, well, yeah! For that, each path is a string of n N's and m E's. Enumerate this in the same way as enumerating all n-size subsets of an n+m set. Reference...
1
2
Replying to
Ah well -- if you want to select among these paths uniformly at random, write the numbers 1 to n+m on separate cards, shuffle the cards, and pick the top n. Go north on those steps, and east on the others.
1