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
I'm actually interested in a second-order problem: count the fraction of paths that go through a particular segment. If you walked to work on a manhattan grid everyday, making random choices, how long before you walked a specific block? A specific sequence of blocks?
5
1
6
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?
1
Show replies
Replying to
The concept of betweenness centrality is kinda relevant to that en.m.wikipedia.org/wiki/Betweenne
1
2
Replying to
heh looks like I'm empircally rediscovering that
Quote Tweet
manhattan grid possible world paths are really pretty if you add a bit of jitter to the path rendering
interesting how if you make random choices (weighted by bounding box side lengths) most paths sorta go through the middle
2
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
Show replies
Replying to
Feels like N! ways.. so that would explode as N increases.
1
Replying to
To amuse myself, I typed this out on my phone while my daughter plays at the park.
Should enumerate all paths.
1





