0

I have trouble to find out an algorithm to pair players with each other.

Assume that after each round new pairings will be generated, the highest rated always play against each other - but they newer play twice agains each other.

Let's say I have the the following players P1, P2, P4, P12, P14 and P16. The Array describes the players they have played the rounds before (3 Rounds already played). The order also describes the current ranking (P1 is first, P16 is last)

P1 = [ 10, 2, 3 ]
P2 = [ 11, 1, 6 ]
P4 = [ 13, 5, 8 ]
P12 = [ 3, 15, 11 ]
P14 = [ 5, 16, 13 ]
P16 = [ 7, 14, 5 ]

You might see, that Player1 already played against Player2. Also Player 14 already played against Player16. No further conflicts.

An approach would be to loop through the the Players-Array (P1 to 16).

P1 --> P2  (not allowed)
P1 --> P4  (Allowed. The Arrays auf P1 and P4 would be appended with the IDs of their opponents)
P2 --> P12 (Allowed, Appending the Arrays auf P2 and P12)
P14 --> P16 (not allowed).

After the first run 2 Players without an allowed Pairing.

I would now say, that I delete the last found pairing and delete the pairings in the arrays and try to find a different combination.

P1 --> P4 (Stays as an allowed pairing from the first loop)
---------
P2 --> P12 (this last allowed pairing would be canceled to find out a different allowed pairing, starting from Player2)
P2 --> P14 (Allowed, Appending the Arrays auf P2 and P14)
P4 --> P16 (Allowed, Appending the Arrays auf P4 and P16)

Result: All Players have allowed Pairings.

My difficulties are how to return to the last allowed pairing to cancel this and to re-search from that point.

Followed by my concern: How could this algorithm even re-re-turn to the first allowed pairing in case that no pairings can be found from Player2.

I have the feeling, that this is something I could solve via a recursion but I have no clue how to set up this recursion (in case, recursion is the answer).

Any help is gratefully appreciated.

Code Examples can be nearly in every Language.

C++ / C# / PHP / Java preferred :-)

Johnny_K
  • 11
  • 3

2 Answers2

0

Few tips:

First if (PX,PY) is an allowed pairing than (PY,PX) is also an allowed pairing.

Second let's assume that generating pairing (PX,PY) also generates pairing (PY,PX) for the sake of generality let's assume that X<Y. Please note that if you do so than when looking for new pairings for PX you only need to seek the pairings for Y which are greater than X (cuz for all lower ones you should have already generated them).

You need also to specify more details.

"Assume that after each round new pairings will be generated, the highest rated always play against each other - but they newer play twice agains each other."

How exactly does generating parings is supposed to work cuz this is a bit to little to understand what you want to accomplish.

user2184057
  • 924
  • 10
  • 27
  • Hello and thank you for your reply! I was aware that (PX,PY) = (PY,PX). And yes, X – Johnny_K Apr 13 '22 at 12:59
  • Ok so to be clear what do you want to do is: Let X be a set of all the players and Y be the set of the matches played so far (in form of pairs (a,b) where a,b are players from X. For the sake of simplicity let's assume that a,b are just numbers (players identifiers) and for every pair a < b. Now what you want is an algorithm whose input data is an ordered List/Array of Players (X) the order decided by current ranking and list/set of all the matches played so far Y. We may also use two dimensional array here. – user2184057 Apr 13 '22 at 13:09
  • One more comment: In my example I use 16 Players that compete in 4 Rounds. After each round the players will be ranked (# wins/loss / # wins of their opponents). In all 4 rounds no one will play twice or more against a different players. Since there only 4 Rounds with 16 Players the amount of 'conflicts' are rather small but nevertheless they exist when trying to pair them. – Johnny_K Apr 13 '22 at 13:10
  • The output of the algorithm should be the list of matches to be played in the current round. The matchmaking logic should always try to match two highest ranked players who don't have yet the match for the current round, it should assign yield a pairing for every player in each round (till everybody has played with everybody or limited by the number of rounds). – user2184057 Apr 13 '22 at 13:12
  • Yes, basically we are speaking about a 2-dim Array Players-Ranking and Players-List-of-historic-Matches/Opponents – Johnny_K Apr 13 '22 at 13:13
  • Yes, your summary what I am trying to achieve is correct. – Johnny_K Apr 13 '22 at 13:14
0

I think I use a different approach.

First I collect all possible combination (disregarding historic pairings). Then I check if this combination tuple is valid or not.

If valid, then I measure the best combination in terms of the distance between the rankings.

Therefore I opened a new question here: Algorithm to return all possible pairings of matches

Johnny_K
  • 11
  • 3
  • In the new question is the solution to even both approaches! – Johnny_K Apr 13 '22 at 16:08
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Apr 14 '22 at 03:53