Нахождение набора перестановок с ограничением

Question

У меня есть набор из 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.

На случай, если вам интересно, для чего это полезно, я ищу алгоритм планирования для коммутатора crossbar с 8 буферами, который обслуживает трафик до 64 пунктов назначения.Эта часть алгоритма планирования не зависит от входного трафика и циклически переключается между рядом встроенных сопоставлений буфера назначения.Цель состоит в том, чтобы каждая пара адресов назначения конкурировала за один и тот же буфер только один раз за период циклирования и максимизировать длину этого периода.Другими словами, чтобы каждая пара адресов конкурировала за один и тот же буфер как можно реже.

---

Редактировать:

Вот какой-то код, который у меня есть.код

Это жадно, обычно оно завершается после нахождения третьей перестановки.Но должен существовать набор по крайней мере из N перестановок, удовлетворяющих задаче.

Альтернатива потребовала бы, чтобы выбор перестановки I включал поиск перестановок (I + 1 ..N), чтобы проверить, является ли перестановка I частью решения, состоящего из максимального числа перестановок.Это потребовало бы перечисления всех перестановок для проверки на каждом шаге, что является непомерно дорогим.

Answer 1

То, что вы хотите, это конструкция комбинаторного блока.Используя номенклатуру на связанной странице, вам нужны проекты размером (n ^ 2, n, 1) для максимального k.Это даст вам n (n + 1) перестановок, используя вашу номенклатуру.Это максимум, теоретически возможный с помощью аргумента подсчета (смотрите объяснение в статье для вывода b из v, k и лямбда).Такие конструкции существуют при n = p ^ k для некоторого простого числа p и целого k с использованием аффинной плоскости.Предполагается, что единственные аффинные плоскости, которые существуют, имеют такой размер.Поэтому, если вы можете выбрать n, возможно, этого ответа будет достаточно.

Однако, если вместо максимально теоретически возможного числа перестановок вы просто хотите найти большое число (максимально возможное для данного n ^ 2), я не уверен, как называется изучение этих объектов.

Answer 2

Создайте массив размером 64 x 64 x 8:bool forbidden[i][j][k], который указывает, появилась ли пара (i, j) в строке k.Каждый раз, когда вы используете пару (i, j) в строке k, вы будете устанавливать связанное значение в этом массиве равным единице.Обратите внимание, что вы будете использовать только ту половину этого массива, для которой я < j.

Чтобы создать новую перестановку, начните с попытки использовать элемент 0 и убедитесь, что по крайней мере семь из запрещенных[0][j][0] не заданы.Если их осталось не семь, увеличьте количество и повторите попытку.Повторите, чтобы заполнить оставшуюся часть строки.Повторите весь этот процесс, чтобы заполнить всю перестановку NxN.

Вероятно, есть оптимизации, которые вы должны быть в состоянии придумать по мере реализации этого, но это должно сработать довольно хорошо.

Answer 3

Возможно, вы могли бы переформулировать свою проблему в теорию графов.Например, вы начинаете с полного графа с N × N вершинами.На каждом шаге вы разбиваете график на N N-кликов, а затем удаляете все используемые ребра.

Для этого случая N = 8 K64 имеет 64 × 63/2 = 2016 ребер, а шестьдесят четыре партии K8 имеют 1792 ребра, так что ваша проблема мочь не быть невозможным :-)

Answer 4

Верно, жадный стиль не работает, потому что у вас заканчиваются цифры.

Легко видеть, что не может быть более 63 перестановок, прежде чем вы нарушите ограничение.На 64-м вам нужно будет соединить хотя бы одно из чисел с другим, с которым оно уже было сопряжено.Принцип разделения по полочкам.

Фактически, если вы воспользуетесь таблицей запрещенных пар, которую я предложил ранее, вы обнаружите, что до того, как у вас закончатся, возможно максимум всего N + 1 = 9 перестановок.Таблица содержит N ^ 2 x (N ^ 2-1) / 2 = 2016 без избыточных ограничений, и каждая новая перестановка создаст N x (N выберите 2) = 28 новых пар.Таким образом, все пары будут израсходованы после 2016/28 = 9 перестановок.Похоже, осознание того, что существует так мало перестановок, является ключом к решению проблемы.

Вы можете сгенерировать список из N перестановок с номером n = 0 ...N-1 как

A_ij = (i * N + j + j * n * N) mod N^2

который генерирует новую перестановку путем сдвига столбцов в каждой перестановке.Верхняя строка n-й перестановки - это диагонали n-1-й перестановки.Редактировать:Упс...кажется, это работает только тогда, когда N является простым числом.

При этом пропускается одна последняя перестановка, которую вы можете получить, транспонировав матрицу:

A_ij = j * N + i