У меня есть набор из N ^ 2 чисел и N ячеек. Каждый бин должен иметь N номеров из назначенного ему набора. Проблема, с которой я столкнулся, заключается в поиске набора распределений, которые отображают числа в ячейки, удовлетворяющие ограничению, согласно которому каждая пара чисел может использовать одну и ту же корзину только один раз.
Распределение может быть хорошо представлено матрицей NxN, в которой каждая строка представляет собой ячейку. Тогда задача состоит в том, чтобы найти набор перестановок элементов матрицы, в котором каждая пара чисел находится в одной и той же строке только один раз. Неважно, какая это строка, только то, что два числа были назначены одному и тому же.
Пример набора из 3 перестановок, удовлетворяющих ограничению для N=8:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
0 8 16 24 32 40 48 56 1 9 17 25 33 41 49 57 2 10 18 26 34 42 50 58 3 11 19 27 35 43 51 59 4 12 20 28 36 44 52 60 5 13 21 29 37 45 53 61 6 14 22 30 38 46 54 62 7 15 23 31 39 47 55 63
0 9 18 27 36 45 54 63 1 10 19 28 37 46 55 56 2 11 20 29 38 47 48 57 3 12 21 30 39 40 49 58 4 13 22 31 32 41 50 59 5 14 23 24 33 42 51 60 6 15 16 25 34 43 52 61 7 8 17 26 35 44 53 62
Перестановка, не принадлежащая указанному выше набору:
0 10 20 30 32 42 52 62 1 11 21 31 33 43 53 63 2 12 22 24 34 44 54 56 3 13 23 25 35 45 55 57 4 14 16 26 36 46 48 58 5 15 17 27 37 47 49 59 6 8 18 28 38 40 50 60 7 9 19 29 39 41 51 61
Из-за множественных столкновений со второй перестановкой, так как, например, они оба соединяют числа 0 и 32 в одной строке.
Перечислить три легко, оно состоит из 1 произвольной перестановки, ее транспонирования и матрицы, в которой строки состоят из диагоналей предыдущей матрицы.
Однако я не могу найти способ создать набор, состоящий из большего количества. Кажется, что это либо очень сложная проблема, либо простая проблема с неочевидным решением. В любом случае я был бы признателен, если бы у кого-нибудь были какие-либо идеи, как решить это в разумные сроки для случая N = 8, или если бы он указал правильное академическое название проблемы, чтобы я мог найти ее в Google.
Если вам интересно, для чего это полезно, я ищу алгоритм планирования для кроссбарного коммутатора с 8 буферами, который обслуживает трафик до 64 пунктов назначения. Эта часть алгоритма планирования не зависит от входного трафика и циклически переключается между несколькими аппаратными отображениями буфера назначения. Цель состоит в том, чтобы каждая пара адресов назначения конкурировала за один и тот же буфер только один раз за циклический период и максимизировала продолжительность этого периода. Другими словами, чтобы каждая пара адресов как можно реже конкурировала за один и тот же буфер.
РЕДАКТИРОВАТЬ:
Вот какой код у меня есть. КОД
Он жадный, обычно завершается после нахождения третьей перестановки. Но должен существовать набор из не менее N перестановок, удовлетворяющих задаче.
Альтернатива потребовала бы, чтобы выбор перестановки I включал поиск перестановок (I+1..N), чтобы проверить, является ли перестановка I частью решения, состоящего из максимального числа перестановок. Это потребовало бы перечисления всех перестановок для проверки на каждом шаге, что непомерно дорого.
