Looping through all combinations

Question

I'm trying to program a multiple players game in Java.

I need to create a list of all combinations and to store these in an array.

If 2 players are logged in as the game start, the combinations are: p1,p2 and p2, p1 (positions are important)

while if 3 players logged in to the game, the combinations are: p1,p2,p3 ; p1,p3,p2 ; p2,p1,p3 ; p2,p3,p1 ; p3,p1,p2 and p3,p2,p1

In fact, I need a redundant array: if 3 players are logged in, I need in advance the combinations of 3 AND the combinations of each possible pairs p1,p2,p3 ; p1,p3,p2 ; p2,p1,p3 ; p2,p3,p1 ; p3,p1,p2 and p3,p2,p1 and p1,p2 and p2, p1 and p1,p3 and p3, p1 and p2,p3 and p3, p2 )

Many players (EDITED: up to 8 players) may be logged in simultaneously to the same round of the game. (EDITED: there are up to 32 groups, but this is not important, because groups are independent)

Is there a quick, short and a simple way to create this combinations array for n players?

A recursive solution is foreseen and acceptable.

Many thanks

P.S.

My ongoing idea is to split the group into 2, a selected pair and the rest of the players. The sekected pairs are selected using 2 FOR loops and the rest with a third. If there are 2 players, no 'rest". If there are 3 players, the 2 FORs will select the positions of the pair and the rest will get the rest. then, the rest are ordered using the same split procedure. May this way get real? how? Will it be efficient? Thanks again.

Try 1: http://stackoverflow.com/questions/4555565/generate-all-subsets-of-size-k-from-a-set — alf, Jan 15 '12 at 17:10
Try 2: http://www.cut-the-knot.org/do_you_know/AllPerm.shtml — alf, Jan 15 '12 at 17:10
A solution may be *short* and *simple*, but there's absolutely no way enumerating through 256! combinations could be *quick*. — Sergey Kalinichenko, Jan 15 '12 at 17:11
Just to elaborate on dasblinkenlight's comment: just for the permutations of 256 players, taht makes 256! possibilities, which evals to 8.58e506: billions of billions of billions ... of possibilities — JB Nizet, Jan 15 '12 at 17:16
And to elaborate on JB Nizet's comment ;) If you could try 100 million different combinations every second, you'd need about `10^491` years for all. The age of the universe is estimated to be about `10^10` years. So I hope you aren't busy.. it may take some time ;) — Voo, Jan 15 '12 at 17:24
@JBNizet My bad. I mixed up the formula for calculating the sum of n numbers (n * (n+1)/2) and the faculty. Of course I tested this for 3!, where the formula works. I thought it was a bit small, so I did the calculation twice ... Will delete my incorrect comment — Robin, Jan 15 '12 at 17:30

score 1 · Answer 1 · answered Jan 15 '12 at 17:18

The number of permutations of size n is n!, which grows exponentially. For example, the number of all permutations of 20 elements is 2432902008176640000(~2.43290201 × 10^18), quite big number.

Like you correctly guessed, there is a recursive algorithm for generating all permutations, but it is quite ineffecient in both time and space for reasons listed above.

However, if your task is generating a random permutation, an efficient algorithm does exist: Fisher–Yates shuffle. It requires O(n) time(assuming you can generate a random integer in O(1)), and O(1) of additional memory.

score 0 · Answer 2 · answered Jan 15 '12 at 17:16

You know the number of entries in each array. For the array with all players, it's 256! That's possibilities for the first entry in the array, 255 for the next, and so forth. 256! is a larger enough number that my calculator can't handle it. Even for 170 players, the size of the array would be 1.3e241. Even on a 64 bit computer, you only have 1.8e19 addressable bytes. This basically means you need to rethink your approach.

Looping through all combinations

2 Answers2