В Германии есть известная карточная игра под названием «Doppelkopf» .
Обычно вы играете «Doppelkopf» с 4 игроками, но вы также можно играть за столом из 5 игроков, где один игрок просто наблюдает.
(где каждый «имеет карты» один раз за раунд, что означает, что каждый имеет право сыграть первую карту один раз в каждый раунд.)
Каждый год моя семья организует турнир «Доппелькопф» с 3 раундами (r).
В зависимости от наличия моих родственников, каждый год количество количество участников различается.
Ожидая минимального количества участников 16 человек, количество (n) в этом эксперименте может расти неограниченно (как и количество раундов r).
Естественно, мои родственники не хотят быть с кем-то дважды в паре, так как хотят максимально эффективно обмениваться сплетнями!
Вот и:
n - Участники
r - Раунды
t_total = n // 4 # Total Tables (round down of n)
t_5 = n % 4 # Tables of 5s
t_4 = t_total - t_5 # Tables of 4s
pos_pair = n * (n - 1) / 2 # possible pairs (n over 2)
nec_pair = (t_5 * 10 + t_4 * 6) * r # necessary pairs
Мне поручили т он стремится минимизировать количество столкновений (если возможно установить встречи == 1 для всех)!
Так как я не хочу решать проблему для P {n = {16, ..., 32}, r = 3 } (что я делал для некоторых случаев), , но чтобы решить эту проблему с любым заданным P {n∈N, r∈N} , есть несоответствие между моими способностями и требованиями к решению!
Поэтому я хотел бы попросить сообщество помочь мне с этой проблемой, решить ее для любого заданного P {n∈N, r∈N}!
А также доказать, неразрешима ли эта задача для любого P {n∈N, r∈N}, которое задано"if pos_pair < nec_pair".
Вот два решения для P {n = 20, r = 3} :
, что очень хорошо решает мою "Doppelkopf" турнирную проблему:
('Best result was ', [[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16], [17, 18, 19, 20]], [[16, 12, 8, 18], [13, 1, 5, 9], [15, 4, 17, 6], [2, 19, 7, 10], [3, 11, 20, 14]], [[14, 9, 17, 7], [13, 20, 8, 2], [5, 4, 12, 19], [6, 16, 11, 1], [15, 18, 10, 3]]])
<br>
('Best result was ', [[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16], [17, 18, 19, 20]], [[19, 11, 13, 3], [2, 15, 9, 8], [1, 16, 18, 6], [14, 7, 17, 10], [4, 12, 20, 5]], [[17, 8, 3, 12], [20, 9, 16, 7], [15, 11, 6, 4], [2, 13, 10, 18], [1, 19, 14, 5]]])
Но чтобы решить эту проблему с произвольными n и r я не пришел к выводу.
На мой взгляд, есть три способа go решить эту проблему в виде вычислительного решения или приближения.
- Во-первых, вы можете перебирать раунды и назначать каждому игроку таблица без коллизий, запоминание пар и внешностей в целом (не для выполнения общих раундов)
- Во-вторых, вы можете перебирать таблицы, что кажется полезным для участников, кратных 2 (см. P {n = 16, r = 5} https://matheplanet.com/default3.html?call=viewtopic.php? Topic = 85206 & ref = https% 3A% 2F% 2F www.google.com%2F)
- также запоминает пары и появления, но в основном следуйте определенным шаблонам, как описано в ссылке, которые я почему-то не могу масштабировать до других чисел !!
- Как-то есть математический способ описать эту процедуру и прийти к решению.
Хотя это скорее математический вопрос (и я не знаю, где задавать эти вопросы), мне интересно в алгоритми c решение!