Finding number of different paths

Question

I have a game that one player X wants to pass a ball to player Y, but he can be playing with more than one player and the others players can pass the ball to Y.

I want to know how many different paths can the ball take from X to Y?

for example if he is playing with 3 players there are 5 different paths, 4 players 16 paths, if he is playing with 20 players there are 330665665962404000 paths, and 40 players 55447192200369381342665835466328897344361743780 that the ball can take. the number max. of players that he can play with is 500.

I was thinking in using Catalan Numbers? do you think is a correct approach to solve this? Can you give me some tips.

Answer 1

EDIT: After more clarification from the comments of the question, my answer is absolutely useless :) he definitely wants the number of possible routes, not the best one!

---

My first thought is why do you want to know these numbers? You're certainly never going to iterate through all the paths available to 500 people (would take far too long) and it's too big to display on a ui in any meaningful way.

I'm assuming that you're going to try to find the best route that the ball can take in which case I would consider looking into algorithms that don't care about the number of nodes in a route.

I'd try looking at the A star algorithm and Dijkstra's algorithm.

Answer 2

At first sight, I would say, that tht number of possible paths can be calculated the following way (I assume a "path" is a sequence of players with no player occuring more than once).

If you play with n+2 players, i.e. player X, player Y and n other players that could occur in the path.

Then the path can contain 0, 1, 2, 3, ... , n-1 or n "intermediate" players between player X (beginning) and player Y (end).

If you choose k (1 <= k <= n) players from n players in total, you can do this in (n choose k) ways.

For each of this subsets of intermediate players, there are k! possible arrangements of players.

So this yields sum(i=0 to n: (n choose i) * i!).

For "better" reading:

---- n     / n \           ---- n      n!            ---- n      1
\          |   |           \        --------         \         ------
/          |   | * i!   =  /         (n-i)!   =  n!  /           i!
---- i=0   \ i /           ---- i=0                  ---- i=0

But I think that these are not the catalan numbers.

Answer 3

I'm somewhat of a noob at this kind of searching, but a quick run through the numbers demonstrates the more you can trim, cut out, filter out, the faster you can do it. The numbers you cite are BIG.

First thing that comes to mind is "Is it practical to limit your search depth?" If you can limit your search depth to say 4 (an arbitrary number), your worst case number of possibilities comes out to ...

499 * 498 * 497 * 496  = 61,258,725,024  (assuming no one gets the ball twice)

This is still large, but an exhaustive search would be far faster (though still too slow for a game) than your original set of numbers.

I'm sure others with more experience in this area would have better suggestions. Still, I hope this helps.

Answer 4

This is really a question in combinatorics, not algorithms.

Mark the number of different paths from player X to player Y as F(n), where n is the number of players including Y but not X. Now, how many different paths are there? Player X can either pass the ball straight to Y (1 option), or pass it to one of the other players (n-1 options). If X passes to another player, we can pretend that player is the new X, where there are n-1 players in the field (since the 'old' X is no longer in the game). That's why F(n) = 1 + (n-1)F(n-1) and F(1) = 1

I'm pretty sure you can reach phimuemue's answer from this one. The question is if you prefer a recursive solution or one with summation.

Answer 5

If X needs to pass to Y, and there could be P1, P2, ..., Pn players in between and you care about the order of passing then indeed

For 2 extra players you have paths: X-Y, X-P1-Y, X-P2-Y, X-P1-P2-Y, X-P2-P1-Y

Which gives a total of 5 different paths, similarly for 3 extra players you have 16 different paths

First try to reduce the problem to something known, and for this I would eliminate X-Y, they are common to all of the above translates to question: what is the sum of k-permutations for k from 0 to n, where n is the number of P.

This can be given as

f(n):=sum(n!/(n-i)!,i,0,n);

and I can confirm your findings for 19 and 39 (20 and 40 in your notation).

For f(499) I get

6633351524650661171514504385285373341733228850724648887634920376333901210587244906195903313708894273811624288449277006968181762616943058027258258920058014768423359811679381900054568501151839849768338994244697593758840394106353734267539926205845992860165295957099385939316593862710470512043836452624452665801937754479602741031832540175306674471495745716725509714798824661807396000105338256698426305553340786519843729411660457896089840381658295930455362209587765698327585913037665131195504013431486823990271059962837959407778393078276213331859189770016153265512805722812864376997337140529242894215031131618375899072989922780132488077015246576266246551484603286735418485007674249207286921801779414240854077425752351919182464902664206622037834736215298295580945851569079682952183639701057397376328170754187008425429164206646365285647875545882646729176997107332605851460212415526607757545366695048460341802079614840254694664267117469603856584752270653889630424848913719533359942725361985274851471687885265903663806182184272555073708882789845441094009797907518245726494471433964169680271980763830020431957658400573531564215436064984091520

Results obtained with wxMaxima