読者です 読者をやめる 読者になる 読者になる

猫尾製作所

あまりアテにしないでね

階乗進数と順列の対応付け

数学 代数学

階乗進法で表した自然数と順列との対応付けについて考えます。

まずは小さな例から考えます。3種類の自然数 {0, 1, 2} を並び替える順列は次の6つでした。6 = 3! です。

012
021
102
120
201
210

これに 0 から 5 までの整数*1を辞書式順に割り振ります。

012 0
021 1
102 2
120 3
201 4
210 5

そして、これに割り振った自然数を 1!, 2! の整数倍の和を用いて表した階乗進数を添えます。

012 0 0 * 2! + 0 * 1!
021 1 0 * 2! + 1 * 1!
102 2 1 * 2! + 0 * 1!
120 3 1 * 2! + 1 * 1!
201 4 2 * 2! + 0 * 1!
210 5 2 * 2! + 1 * 1!

さて、ちょっと端折りますが。ここで階乗進数から順列へ次のような方法で対応付けます。

例えば、階乗進数 85 = 3 * 4! + 2 * 3! + 0 * 2! + 1 * 1! と 5種類の自然数 {0, 1, 2, 3, 4} の並び替えからなる順列への対応付けという具体例で示します。

階乗進数の各桁 3, 2, 0, 1 について a[4] = 3, a[3] = 2, a[2] = 0, a[1] = 1 とします。また S = { 0, 1, 2, 3, 4 } という順序つきのリストを考えます。S[i] で先頭を 0 番として、リストの先頭から数えて i 番目の要素(例えば、初期状態では S[2] = 2)を表すものとします。そして、空のリスト T = {} を作成します。

  • まず最初は、S = { 0, 1, 2, 3, 4 } ですが、a[4] = 3 より S[3] = 3 を取り出して T にそれを追加します。T = { 3 } となります。そして S[3] = 3 はリストから削除してそれを詰めます。
  • 次には S = { 0, 1, 2, 4 } となりますが、a[3] = 2 より S[2] = 2 を取り出し、同様に T に追加し、T = { 3, 2 } となります、そして S[2] = 2 はリストから削除してそれを詰めます。
  • 次には S = { 0, 1, 4 } となりますが、a[2] = 0 より S[0] = 0 を取り出し、同様に T に追加し、T = { 3, 2, 0 } となります、そして S[0] = 0 はリストから削除してそれを詰めます。
  • 次には S = { 1, 4 } となりますが、a[1] = 1 より S[1] = 4 を取り出し、同様に T に追加し、T = { 3, 2, 0, 4 } となります、そして S[1] = 4 はリストから削除してそれを詰めます。
  • 最後に残った S の唯一の元 1 を T に追加し { 3, 2, 0, 4, 1 } を得て、これを対応する順列とするのです。

蛇足ながら、もう一つ例を

n = 2 * 5! + 0 * 4! + 2 * 3! + 2 * 2! + 0 * 1! = 256
a[5] = 2, a[4] = 0, a[3] = 2, a[2] = 2, a[1] = 0
S = { 0, 1, 2, 3, 4, 5 }
とすると

  • S[a[5]] = S[2] = 2
  • S ← { 0, 1, 3, 4, 5 }
  • T ← { 2 }
  • S[a[4]] = S[0] = 0
  • S ← { 1, 3, 4, 5 }
  • T ← { 2, 0 }
  • S[a[3]] = S[2] = 4
  • S ← { 1, 3, 5 }
  • T ← { 2, 0, 4 }
  • S[a[2]] = S[2] = 5
  • S ← { 1, 3 }
  • T ← { 2, 0, 4, 5 }
  • S[a[1]] = S[0] = 1
  • S ← { 3 }
  • T ← { 2, 0, 4, 5, 1 }
  • 最後に T ← { 2, 0, 4, 5, 1, 3 }

よって、n = 2 * 5! + 0 * 4! + 2 * 3! + 2 * 2! + 0 * 1! = 256 に対して6個の元からなる順列 204513 を得ます。

この逆変換は

最初に
T = { 2, 0, 4, 5, 1, 3 }, S = { 0, 1, 2, 3, 4, 5 } とします。

  • T[0] = 2 は S の何番目? → 2 : a[1]
  • S から 2 を削除し、S = { 0, 1, 3, 4, 5 }
  • T[1] = 0 は S の何番目? → 0 : a[2]
  • S から 0 を削除し、S = { 1, 3, 4, 5 }
  • T[2] = 4 は S の何番目? → 2 : a[3]
  • S から 4 を削除し、S = { 1, 3, 5 }
  • T[3] = 5 は S の何番目? → 2 : a[4]
  • S から 5 を削除し、S = { 1, 3 }
  • T[4] = 1 は S の何番目? → 0 : a[5]
  • S から 1 を削除し、S = { 3 }
  • 終了

ちょっと説明がうまくいっていないので、次に Ruby でのプログラミングでアルゴリズムを明確に示します。

*1:0 も自然数に含めるということにすれば、自然数と言い換えることが出来ます。