Algorithm for Pairing Combinations in Arrays-CodePudding

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 :-)

CodePudding user response：

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.

CodePudding user response：

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