Как расставить пары с условием за преемлемое время (380! комбинаций)?

Question

[zzox4]

Есть 20 команд которые должны играть с друг другом парами (1 - 4 раза), т.е. итого 20*19 = 380 матчей (при 2х играх для пары).
Есть несколько свободных слот на каждый день - т.е. место и время
Условие: если команда играет в этот день, то у неё должно быть минимум 2 игры (не должно быть ровно одной игры в день), либо 0 либо 2+ игры.

Как найти расстановку матчей (расписание) при минимальном кол-ве дней (либо приемлемый результат, минимальный + 10%), за приемлемое время?

Если просто перебирать все варианты то это 380! что не реально проверить.
Я сделал решение которое делает расстановку за O(N*M) (матчи х слоты), методом решета и спроса, но без условия "минимум 2 игры в день".

Если применить условие, то мой алгоритм не находит решения.
Куда копать, какие есть варианты?

Сейчас в голове 2 направления:
* Рекурсивный перебор + оптимизации (какие? те же отсечения решета и спроса?)
* Сделать готовые патерны расстановок и применять их

Answer 1

[Александр Маджугин]

Или я не понял условие или...
А что здесь какого-то сложного? Минимальное количество дней обеспечит максимальная загрузка слотов ежедневно.
Если слотов четное количество (n). То на каждом шаге выбираем n/2 пар которые еще не играли и они отыгрывают обе свои игры.

Если слотов нечетное количество то на нечетном шаге выбираем (n-1)/2 пар которые еще не играли и они отыгрывают обе свои игры + 1 пару которая еще не играла и она играет 1 игру.
На четном шаге мы выбираем (n-1)/2 пар которые еще не играли и они отыгрывают обе свои игры и одну единственную пару которая сыграла свою одну игру на прошлом шаге - она отыгрывает вторую свою игру.

Всё.

Comments

[zzox4]

и они отыгрывают обе свои игры.

И правда, для 2-х пар игр получается просто, я поправил условие (игр может быть 1 и более), слотов каждый день разное кол-во. (а в итоговом требовании ещё больше нюансов, типа некоторые матчи знимают несоклько слотов, а не один, некоторые слоты могут вместить более 1 матча и быть на расстоянии друг от друга по времени и т.п.)

Но в целом направление понятно, нужно сделать ряд патернов и их отрабатывать.