Перестановки большого количества строк

Массив int (от 0 до 30) имеет N строки и 4 столбца.

Оно имеет head и tail, начало и конец.

Все строки, кроме двух, должны быть переставлены между head и tail, Строки, обозначенные как head и tail можно перемещать, но расстояние между ними должно быть одинаковым, сверху вниз.

Пример:

введите описание изображения здесь

На этой картинке последовательность { 2, 4, 7, 9 } это head, { 7, 1, 9, 4 } это tail, Таким образом, только элементы между этими двумя могут быть перемешаны строка за строкой (не столбец за столбцом).

(Следует отметить, что «Row #» относится к строке, которая содержит соответствующие последовательности, а не абсолютные строки с нашей точки зрения. Тогда «Row3» на этом рисунке расположен во второй строке).

Теоретически, если я прав, их 3! возможные перестановки.

Но эти элементы не могут быть случайно перемешаны. Требуется конкретная конфигурация.

Первое противопоказание: каждый ИНТ из второй столбец (здесь: ColB) должен быть идентичен int, расположенному в x mod N ряды под ним в первый колонка (ColA). (x произвольно: мы знать что есть решение для данного x).

Второе ограничение: Каждый int из в третьих столбец (ColC) должен быть идентичен int чуть ниже, мод N (тогда, NC = 1D), в четвертый колонка (ColD).

Пример хорошей конфигурации (x = 3 Вот):
введите описание изображения здесь

Возьмите номер 4, row1, colB. Это идентично номеру, расположенному в ((row where is 4)+3) % 5, colA (синим цветом). И это также относится ко всем номерам ColB.

Возьмите номер 7, row1, colC. Это идентично номеру, расположенному в ((row where is 7)+1) % 5, colD (желтым цветом).

Это тоже хорошая конфигурация (x = 3 тоже):

введите описание изображения здесь

Head а также tail были перемещены, но расстояние сверху вниз (мы начинаем с head конечно) между двумя остается одинаковым.

Возьмите номер 2, row3 (затем четвертый ряд), colB. Это идентично номеру, расположенному в ((row where is 2)+3) % 5 = второй ряд, colA.

Как видите, в этой ситуации решить очень просто, тривиально.

Теперь представьте, что N = 300. 300-2 строки должны быть переставлены, чтобы соответствовать ограничениям. Тогда 298! возможны перестановки. Это кажется неразрешимым.

Знаете ли вы, если алгоритм может помочь решить эту проблему с N = 300 строк с повторением intв разумный время (то есть < возраст Вселенной)?

Спасибо!

1

Решение

Задача ещё не решена.

Другие решения


По вопросам рекламы [email protected]