CODEWITHSUNDEEP
javaloopsrecursion
elarrow
elarrow

Reputation: 697

Looping through all combinations

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.

Upvotes: 0

Views: 3122

Answers (2)

Alexander Putilin
Alexander Putilin

Reputation: 2342

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.

Upvotes: 1

Mike
Mike

Reputation: 3084

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.

Upvotes: 0

Related Questions