Переупорядочивающий ввод с использованием того же шаблона, пока он не изменится обратно к первоначальному заказу

Question

Я нашел этот вопрос для интервью и задаюсь вопросом, есть ли какой-либо хороший способ его решения. У нас есть входной массив [0, 1, 2, 3] и массив шаблонов, например. [3,1,2,0], то, что делает массив шаблонов, заключается в том, что мы должны изменить порядок ввода, поместив элемент в индекс 3 в первую позицию, затем поместите элемент в индекс 1 во вторую позицию и т. Д. Таким образом, после одной итерации [0, 1, 2, 3] станет [3, 1, 2, 0], после очередной итерации переупорядочения с использованием того же шаблона она снова станет [0, 1, 2, 3].

Вопрос в том, сколько раз нам нужно повторять заданный шаблон, чтобы он возвращался к первоначальному порядку, и возможно ли, что входной массив никогда не может вернуться к первоначальному порядку, учитывая определенный порядок переупорядочения?

---

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

Answer 1

Существует обозначение перестановок, называемых циклическими обозначениями, которые помогут вам в этом случае. Циклическая обозначение для примера шаблона:

(0 3) (1 2) 

Это означает: запись в положении 0 идет в положении 3. Вход в позицию 3 переходит в положение 0 (просто оберните). Вход в позицию 1 идет в 2 и 2 переходит на 1. Кроме того, можно получить большие циклы, например .:

(0 3 1) (2) 

Для этой перестановки, то результат будет выглядеть следующим образом:

 a b c d 
It 1: b d c a 
It 2: d a c b 
It 3: a b c d 

Так в этом случае требуется три итерации, чтобы вернуться к исходному порядку. Это число может быть получено непосредственно из циклического обозначения. В первом примере есть два цикла с двумя входами каждый. Количество требуемых общих циклов является наименее общим числом lcm(2, 2) = 2. Во втором примере это lcm(3, 1) = 3.

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