У меня есть набор из 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.
В случае, если вам интересно, для чего это полезно, я ищу алгоритм планирования для коммутатора с двумя буферами, который обслуживает трафик до 64 пунктов назначения. Эта часть алгоритма планирования не зависит от входного трафика и циклически переключается между несколькими жестко привязанными сопоставлениями целевого буфера. Цель состоит в том, чтобы каждая пара адресов назначения конкурировала за один и тот же буфер только один раз за период цикла, и чтобы максимизировать длину этого периода. Другими словами, чтобы каждая пара адресов конкурировала за один и тот же буфер как можно реже.
EDIT:
Вот некоторый код, который у меня есть.
КОД
Жадный, обычно заканчивается после нахождения третьей перестановки. Но должен существовать набор по крайней мере из N перестановок, удовлетворяющих задаче.
Альтернатива потребовала бы, чтобы при выборе перестановки я искал перестановки (I + 1..N), чтобы проверить, является ли перестановка I частью решения, состоящего из максимального числа перестановок. Это потребовало бы перечисления всех перестановок для проверки на каждом шаге, что непомерно дорого.