Сортировка двумерного тороидального массива с вращениями и перестановками

Question

Я пытался придумать алгоритм, но не смог этого сделать.Вот проблема:

Существует 16 элементов, сгруппированных по четырем типам (a, b, c и d).У нас также есть четыре группы, A, B, C и D.

В исходном состоянии четыре группы имеют четыре случайных элемента в каждой, например ::

A: c, c, a, d
B: b, b, a, a
C: b, b, c, c
D: d, d, d, a

Порядок элементовв группе значимы.

Допускается две операции:

1) вращение элементов группы (в обе стороны), например ::

c, c, a, d -> d, c, c, a

2) поменять местами два смежных элемента в группе с соответствующими элементами в смежной группе, учитывая, что первая и последняя группы и элементы также являются смежными, поэтому:

Цель алгоритма - поместить элементы в соответствующие группы (A: a, a, a, a и т. Д.).Алгоритм не должен быть оптимальным с точки зрения времени и решения, но в среднем он должен быть достаточно быстрым (т. Е. Без перебора).

Кто-нибудь может помочь?Является ли этот алгоритм даже полиномиальным?

Answer 1

Я думаю, что это всегда возможно. Сначала рассмотрим случай, когда буква (скажем, b) появляется только в двух строках X и Y. Мы можем убедиться, что X и Y соседствуют с операциями обмена.

Дело I)

X: b - - -
Y: - b b b

Мы можем сделать X всех б

Cyclich Shift X.

X: - - b - 
Y: - b b b

поменять середину

X: - b b -
Y: - - b b

Теперь циклический сдвиг и своп.

Случай II)

X: b - b -
Y: b - b -

сделай это

X: - b - b
Y: b - b -

Поменяйте местами последние два.

Другой случай тривиален.

Теперь, учитывая любое распределение конкретной буквы в 2,3 или 4 рядах, мы можем гарантировать, что она появляется только в двух строках. Я оставлю это вам, так как это легко увидеть и сложно напечатать!

(Если оно появляется только в одном ряду, наша работа в основном выполняется для этого письма)

Таким образом, алгоритм будет

Убедитесь, что a появляется только в двух строках. Убедитесь, что строки A и B (поменяйте местами позже).

Теперь выполните упражнение выше, чтобы сделать A аааа.

Игнорировать А.

Рассмотрим B, C, D. Убедитесь, что b отображается только в двух строках. Сделайте B как bbbb, как указано выше.

Игнорировать Б.

Учитывая C и D, вы можете использовать вышеупомянутое, чтобы C было cccc, D будет dddd.

Answer 2

Моя первоначальная идея состояла в том, чтобы попытаться использовать какую-либо форму динамического программирования - проблема кажется относительно похожей на Изменить расстояние в том, что у вас есть ограниченный набор операций и известное желаемое конечное состояние. Подход динамического программирования привел бы к получению алгоритма много времени. Но, как я уже сказал, именно здесь я бы начал искать алгоритм, я не знаю, сработает ли этот подход. Если я получу время спустя, у меня будет более глубокая мысль.

Надеюсь, это поможет!