Search on the blog

2011年5月9日月曜日

完全順列とモンモール数

数列
 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 件のコメント:

コメントを投稿