Нахождение ряда перестановок, с ограничением
Поскольку необходимо установить line-height на высоту отделения для этого для работы
4 ответа
What you want is a combinatorial block design. Using the nomenclature on the linked page, you want designs of size (n^2, n, 1) for maximum k. This will give you n(n+1) permutations, using your nomenclature. This is the maximum theoretically possible by a counting argument (see the explanation in the article for the derivation of b from v, k, and lambda). Such designs exist for n = p^k for some prime p and integer k, using an affine plane. It is conjectured that the only affine planes that exist are of this size. Therefore, if you can select n, maybe this answer will suffice.
However, if instead of the maximum theoretically possible number of permutations, you just want to find a large number (the most you can for a given n^2), I am not sure what the study of these objects is called.
Создайте массив размером 64 x 64 x 8: bool запрещено [i] [j] [k], который указывает, появилась ли пара (i, j) в строке k. Каждый раз, когда вы используете пару (i, j) в строке k, вы устанавливаете связанное значение в этом массиве равным единице. Обратите внимание, что вы будете использовать только половину этого массива, для которого i Чтобы построить новую перестановку, начните с попытки члена 0 и убедитесь, что по крайней мере семь из запрещенных [0] [j] [0] которые не установлены. Если осталось не семь, увеличьте и попробуйте снова. Повторите, чтобы заполнить оставшуюся часть ряда. Повторите весь этот процесс, чтобы заполнить всю перестановку NxN. Вероятно, вы сможете провести оптимизацию, когда реализуете это, но это должно сработать очень хорошо.
Возможно, вы могли бы переформулировать вашу проблему в теории графов. Например, вы начинаете с полного графа с N × N вершинами. На каждом шаге вы разбиваете граф на N N-клик, а затем удаляете все использованные ребра.
Для этого случая N = 8, K64 имеет 64 × 63/2 = 2016 ребер, а шестьдесят четыре партии K8 имеют 1792 ребра, поэтому ваша проблема может не быть невозможной: -)
Верно, жадный стиль не работает, потому что у вас заканчиваются числа.
Легко видеть, что не может быть более 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