元の順序に戻すまで同じパターンを使用した入力の並べ替え

Question

私はこのインタビューの質問を見つけ、それを解決する良い方法があるかどうか疑問に思います。我々は入力配列[0,1,2,3]とパターン配列を持っている。 [3,1,2,0]パターン配列がしていることは、3のインデックスの要素を最初の位置に置き、1のインデックスの要素を2番目の位置に置くなどして入力を並べ替えるべきことです。 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になります。

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

をので、この場合は、元の順番に取得するには3回の反復を必要とします。それは次のように、結果が見えるこの順列のために、より大きなサイクル、例えば：

(0 3 1) (2) 

を取得することも可能です。この数は、循環表記法から直接導き出すことができます。最初の例では、それぞれ2つのエントリを持つ2つのサイクルがあります。必要な総サイクル数は、最小公倍数であるlcm(2, 2) = 2です。 2番目の例では、lcm(3, 1) = 3です。

そして、循環表記を導出することはあまり難しくありません。パターンを繰り返し処理するだけです。まだサイクルの一部ではないエントリに遭遇した場合は、そのパターンに従ってパスをたどり、サイクルの長さを覚えておいてください。これにより、含まれるすべてのサイクルの長さがわかります。最後に、LCMを計算し、その結果として報告する。