Ai, 1 <= i <= n
が条件
Ai != i, 1 <= i <= n
を満たす場合、Aを完全順列（またの名を乱列）と呼びます。例えば、3, 1, 2など。
そして長さnの完全順列のパターン数をXnとすると、X1, X2, X3, ....をモンモール数列と呼びます。
実は、このモンモール数はアルゴリズムコンテストによく出ます。最近だと、Facebook Hacker Cup 2011、Google Code Jam2011に出て来ました。
長さi-1の完全順列の後ろに要素を1つ足して、最後の1つと別の任意の要素を入れ替えると、それは長さiの完全順列になります。加えて、1箇所を除けば完全順列になっているような長さi-1の数列に、1つ要素を加えて、Ai = iとなっている要素と入れ替えると、それも完全順列になります。
以上のことから、第i番目のモンモール数列は、
Xi = (i-1) * (Xi-1 + Xi-2)
と書けます。
X1 = 0, X2 = 1は自明。
コンピュータ上で実装する場合は、フィボナッチ数列と同じようにメモ化再帰 OR 動的計画（末尾再起）で書くとよいです。また、見てのとおりとても大きな数になるので、Moduloを取って計算させる問題が多いみたいです。
0 件のコメント:
コメントを投稿