Какой алгоритм рассадки игроков по нескольким столам с условиеми в описании?

Question

[MayRiv]

Есть 25 команд по 4 человека в каждой. Игроки одной команды не должны сидеть за одним столом.
Есть 10 столов, каждый вмещает 10 игроков.
Каждый игрок должен сыграть 10 игр, и желательно, чтобы игроки сыграли примерно одинаковое количество игр друг с другом(если это возможно). Желательно, чтобы каждый игрок сыграл хотя бы раз с остальными игроками(кроме членов своей команды).

На скрине старая рассадка, но она паршивая - большое количество игроков друг с другом не играют вообще.

Comments

[Макс]

в игре участвуют сразу все 10 игроков за столом? Если нет - последнее условие не выполнимо. всего 96 игроков из "чужих" комманд, за 10 игр можно съиграть со всеми только если в игре участвуют по 10 человек.

[MayRiv]

Макс: 10 столов. Перепутал случайно. да, одновременно за столом играют 10 человек.

[Андрей]

Вас интересует единоразовое решение этой задачи или возможность создавать все новые и новые рассадки по мере необходимости ?

[MayRiv]

Андрей: Задача минимум - единоразовое решение проблемы.
Идеально - возможность создавать все новые и новые рассадки для разного количества игроков и столов. Метод создания рассадок очень интересует, у меня нет идей как правильно решать эту задачу, если не рандомом формировать массив, проверяя подходит ли он под ограничения:)

Answer 1

[Андрей]

Задача минимум - единоразовое решение проблемы.
Идеально - возможность создавать все новые и новые рассадки для разного количества игроков и столов. Метод создания рассадок очень интересует, у меня нет идей как правильно решать эту задачу, если не рандомом формировать массив, проверяя подходит ли он под ограничения:)

Ваши условия дают на конечный массив слишком много ограничений, поэтому при проверке уже готового рандомного массива он с вероятностью 99.999% не будет Вас устраивать. Поэтому либо массив должен заполняться постепенно с проверкой каждой новой ячейки на все уже возникшие при ее заполнения ограничения и возможным откатом назад (и весьма далеко), если все ветви далее по ходу заполнения окажутся тупиковыми. Либо как мне кажется неплохо должен сработать на этой задаче генетический алгоритм заполнения - Вы задаете случайную начальную рассадку и вычисляете суммарный штраф за все нарушения условий (при чем можете задать очень большие "заградительные" штрафы за абсолютно недопустимые условия), а затем оптимизируете изменяя построчно/по столбцам минимизируя штраф.

Comments

[MayRiv]

Интересный вариант, попробую реализовать в ближайшее время. Ответом пока не помечаю, надеюсь на математически красивый точный метод решения.