동일한 순서로 입력을 재정렬하여 원래 순서로 다시 바꿀 때까지

Question

이 인터뷰 질문을 발견하고이를 해결할 좋은 방법이 있는지 궁금합니다. 우리는 입력 배열 [0, 1, 2, 3]과 패턴 배열을 가지고 있습니다. [3,1,2,0] 패턴 배열이하는 일은 3의 인덱스에있는 요소를 첫 번째 위치에 놓고 1의 인덱스에있는 요소를 두 번째 위치에 놓음으로써 입력을 재정렬해야한다는 것입니다. 따라서 [0, 1, 2, 3]은 [0,1,2,3]이되고, 동일한 패턴을 사용하여 다시 순서를 반복하면 [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을 계산하고 그 결과로보고하십시오.