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
Replying to
Ah ok, that's the formula I derived, but wasn't entirely sure of my logic, thanks... any idea how to enumerate them systematically?
Replying to
an easy way to enumerate them would be depth-first traversal of a binary decision tree, where you only take up to N x-moves and up to M y-moves, and bottom out when you've taken all of both
2

