Z
Z
zzox42018-08-17 18:58:21
Algorithms
zzox4, 2018-08-17 18:58:21

How to arrange pairs with a condition in acceptable time (380! combinations)?

There are 20 teams that must play each other in pairs (1 - 4 times), i.e. total 20 * 19 = 380 matches (with 2 games for a couple).
There are several free slots for each day - ie. place and time
Condition: if a team plays on this day, then it must have at least 2 games (should not have exactly one game per day), or 0 or 2+ games.
How to find the arrangement of matches (schedule) with a minimum number of days (or an acceptable result, minimum + 10%), in an acceptable time?
If you just sort through all the options, then this is 380! which is not really verifiable.
I've made a solution that does O(N*M) (matches x slots), sieve and demand method, but without the "minimum 2 games per day" condition.
If the condition is applied, then my algorithm does not find a solution.
Where to dig, what options are there?
Now there are 2 directions in my head:
* Recursive enumeration + optimizations (what? Same sieve and demand cutoffs?)
* Make ready-made constellation patterns and apply them

Answer the question

In order to leave comments, you need to log in

1 answer(s)
A
Alexander, 2018-08-17
@zzox4

Either I didn't understand the condition, or...
What's so complicated about it? The minimum number of days will ensure the maximum loading of slots daily.
If there is an even number of slots (n). Then at each step we select n/2 pairs that have not yet played and they play both of their games.
If there is an odd number of slots, then at an odd step we select (n-1) / 2 pairs that have not yet played and they play both of their games + 1 pair that has not yet played and it plays 1 game.
At an even step, we choose (n-1)/2 pairs that have not played yet and they play both of their games and one single pair that played its one game at the last step - it plays its second game.
Everything.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question