У нас есть n уникальных элементов. Допустим, n = 8 и N = {A, B, C, D, E, F, G, H} .
Мы хотим получить все уникальные комбинации этих элементов, в данном случае это должно дать 28 уникальных пар.
[A, B]
[A, C]
[A, D]
[A, E]
[A, F]
[A, H]
[A, G]
[B, C]
[B, D]
[B, E]
[B, F]
[B, H]
[B, G]
[C, D]
[C, E]
[C, F]
[C, H]
[C, G]
[D, E]
[D, F]
[D, H]
[D, G]
[E, F]
[E, H]
[E, G]
[F, H]
[F, G]
[H, G]
Затем мы хотим взять эти пары и сгруппировать их в x группы из y пар. Пусть X = 7 и Y = 4 . Ни одна группа не должна иметь элемент, представленный более одного раза, и ни одна пара не должна использоваться более одного раза во всех x группах.
Простой алгоритм грубой силы падает здесь - он создает 4 группы по 4, 3 группы по 3, при этом 3 пары не могут быть сгруппированы. Это происходит последовательно.
***** Group 1 *****
Pair(element1=F, element2=G)
Pair(element1=E, element2=H)
Pair(element1=C, element2=D)
Pair(element1=A, element2=B)
***** Group 2 *****
Pair(element1=F, element2=H)
Pair(element1=E, element2=G)
Pair(element1=B, element2=C)
Pair(element1=A, element2=D)
***** Group 3 *****
Pair(element1=E, element2=F)
Pair(element1=D, element2=G)
Pair(element1=C, element2=H)
***** Group 4 *****
Pair(element1=D, element2=E)
Pair(element1=C, element2=F)
Pair(element1=B, element2=G)
Pair(element1=A, element2=H)
***** Group 5 *****
Pair(element1=D, element2=F)
Pair(element1=C, element2=E)
Pair(element1=B, element2=H)
Pair(element1=A, element2=G)
***** Group 6 *****
Pair(element1=D, element2=H)
Pair(element1=C, element2=G)
Pair(element1=B, element2=E)
Pair(element1=A, element2=F)
***** Group 7 *****
Pair(element1=B, element2=D)
Pair(element1=A, element2=C)
Pair(element1=H, element2=G)
Мы могли бы удвоить подход грубой силы и просто отбросить неудачную окончательную группировку, рандомизировать порядок уникальных пар и повторить попытку, но должен быть более чистый (более умный) способ сделать это.
Делая небольшую копку, я думаю, что это может быть проблемой Точное покрытие . Это точное обобщение здесь? Если это так, я могу перенаправить свои усилия на реализацию алгоритма X. Я скептически отношусь, потому что я не просто ищу точное покрытие, я ищу точное покрытие, где каждое подмножество имеет одинаковый размер.
Я понимаю, что эта проблема выглядит подозрительно, как домашняя работа, но я давно не в школе. Хотите верьте, хотите нет, но это всего лишь пара разработчиков, пытающихся сгенерировать расписание парного программирования - с треском провалившихся - и понимающих, что мы натолкнулись на немного интересную проблему.
Спасибо.