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?
Conversation
Replying to
Yep. All this follows neatly from the same logic by which Pascal's Triangle enumerates binomial coefficients. en.wikipedia.org/wiki/Binomial_
2
3
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
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
1
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
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
I have stanley's enumerative combinatorics books for a retirement project :D
until then, I use randomized algos because I'm too dumb to use the deterministic ones based on the right formulas
1
Show replies

