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
all equivalent shortest paths have N x-steps and M y-steps, which you can take in any order, so i think it's just (N+M)!/N!M!
1
3
This Tweet was deleted by the Tweet author. Learn more
nah, it's a question of permuting a list of N identical L-choices and M identical R-choices, so you have (N+M)! total orderings and then a factor of N! redundant orderings for the identical Ls and a factor of M! redundant orderings for the Rs
1
1
Replying to
Yes, the formula has to be symmetric in M and N so the Kshitij's formula is wrong by inspection :D

