Как разделить список на меньшие списки, чтобы вероятность того, что один элемент столкнется с другим элементом, была равномерно распределена?

#python #algorithm #combinatorics

#python #алгоритм #комбинаторика

Вопрос:

Я борюсь с алгоритмом разделения группы участников на более мелкие группы для составления раундов. Возьмем, к примеру, группу из 20 человек, которую я хочу разделить на 3 группы (7,7,6). В каждом раунде соревнования группы разные, так что каждому приходится сражаться со всеми остальными в довольно справедливом распределении.

Проблема в том, что при (наивном) случайном выборе одному человеку приходится сражаться с одним и тем же человеком чаще, чем с другим. Т.е. два элемента часто оказываются в одной группе.

Я хотел бы сделать это более справедливым, чтобы для заданного количества участников, размера группы (не все группы одинакового размера) и количества раундов алгоритм находил справедливый набор групп за раунд, так что в среднем у каждого участника были одинаковые шансы встретить одного и того же участника во время раундов.

Есть ли какая-либо литература по этой теме, с которой я могу проконсультироваться? Или какие-либо известные алгоритмы?

Ответ №1:

Вы переходите к теме, которая была исследована в combinatorics, но на самом деле создание этих конструкций на удивление сложно. Смотрите http://en.wikipedia.org/wiki/Block_design вот пример того, о чем вы захотите узнать больше. Если вам нужна помощь, я предлагаю спросить на https://math.stackexchange.com / потому что у вас будет больше шансов найти кого-то, кто помнит этот материал. (Мне не приходилось смотреть на этот материал в этом тысячелетии, иначе я бы сказал об этом что-нибудь более полезное.)

Ответ №2:

вы можете взглянуть на этот метод: random.sample(population, k)