PHP - равномерно распределяйте команды по массивам, чтобы не повторялась комбинация

Question

У меня есть следующие девять команд для события:

array('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I')

Для каждого матча в этом событии требуется три команды-участника (то есть: A против B против C).Каждая команда должна играть с каждой другой командой один раз и только один раз.

Для вышеупомянутых девяти команд будет четыре раунда (каждая команда сыграет две другие команды за матч, и для каждой команды будет восемь команд - 8/2 = 4 раунда) и всего двенадцатьсовпадения во всех четырех раундах (в каждом раунде по три матча по три команды в каждой - 4 раунда по 3 матча = 12 матчей).

Мой ожидаемый выходной формат:

array('A', 'B', 'C')
array('D', 'E', 'F')
array('G', 'H', 'I')
etc...

.выше всего будет двенадцать массивов.

Как бы вы распределили вышеупомянутые девять команд по двенадцати отдельным массивам (каждый массив, представляющий совпадение), чтобы каждая команда играла в каждой другой команде один раз и только один раз?

Answer 1

Альтернативный подход состоит в том, чтобы рассматривать это как систему ограничений.Такая проблема может быть решена с помощью решателя ограничений.Эту проблему иногда называют проблемой социального игрока в гольф (Google найдет много ссылок).Математическая модель может выглядеть следующим образом:

Индексы:

  t in {A,..,I}  (team)
  r in {round1,..,round4}
  m in {match1,..,match3}

Двоичная переменная:

x(r,m,t) in {0,1}  (indicates if team t plays in round r, match m)

Ограничения:

sum(m,x(r,m,t)) = 1 for all r,t                    (team plays exactly once in a round)
sum(t,x(r,m,t)) = 3 for all r,m                    (three teams in a match)  
sum((r,m), x(r,m,t1)*x(r,m,t2)) <= 1 for all t1<t2 (teams play once in same match)

Это может бытьрешается с помощью решателя ограничений или MIQCP (смешанного целочисленного квадратично-зависимого программирования).(В последнем случае добавьте фиктивную цель).Последнее квадратичное ограничение может быть линеаризовано, и в этом случае мы также можем решить его с помощью решателя линейного MIP (Mixed Integer Programming).

Мое решение выглядит так:

----     33 VARIABLE x.L  

                        A           B           C           D           E           F           G           H           I

round1.match1                       1                                                           1           1
round1.match2                                   1                                   1                                   1
round1.match3           1                                   1           1
round2.match1           1                                                           1           1
round2.match2                       1                       1                                                           1
round2.match3                                   1                       1                                   1
round3.match1                       1                                   1           1
round3.match2           1                                                                                   1           1
round3.match3                                   1           1                                   1
round4.match1           1           1           1
round4.match2                                               1                       1                       1
round4.match3                                                           1                       1                       1

Answer 2

Подобные проблемы подпадают под теорию проектирования.Я думаю, что в данном случае то, что называется системой Штейнера S (2,3,9)

123, 456, 789, 147, 258, 369, 159, 267, 348, 168, 249 и 357.

Где я вырезал и вставил из http://users.mct.open.ac.uk/mjg47/papers/IntroSteiner.pdf в надежде избежать опечаток.

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