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

猫尾製作所

あまりアテにしないでね

順列と自然数の対応付け

数学 代数学

前回の続きです。

前回の記事では3つのものを並び替える順列をお盆休みの予定(墓参り, 海水浴, 図書館)の配分という具体例で持って表現しました。そして、その予定の配分には6通りあることも示しました。

この3つの予定を抽象的なもの、例えば整数で置き換えてみます。なお、このあとはプログラミングを行うことを考えているので、自然数とは 0 以上の整数全体のことにいたします。

3つの自然数の集合 { 0, 1, 2 } に対しての順列を考えます。前回の記事の { 墓参り, 海水浴, 図書館 } の予定を { 0, 1, 2 } でもって置き換えるのです。すると順列の全ては以下のようになります。

(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)

では、4つの自然数からなる集合 S = { 0, 1, 2, 3 } に対しての順列を次のような方法で生成します。

  • まず 4 つの自然数(S の元)の中からひとつ選んで1マス目に書く(使った自然数は S から削除する)
  • 残りの 3 つの自然数の中から一つ選んで2マス目に書く(使った自然数は S から削除する)
  • 残りの 2 つの自然数の中から一つ選んで3マス目に書く(使った自然数は S から削除する)
  • 最後に残った自然数を4マス目に書く。

この方法で出来うる順列の全ては以下のようになります。

(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), 
(1, 0, 2, 3), (1, 0, 3, 2), (1, 2, 0, 3), (1, 2, 3, 0), (1, 3, 0, 2), (1, 3, 2, 0), 
(2, 0, 1, 3), (2, 0, 3, 1), (2, 1, 0, 3), (2, 1, 3, 0), (2, 3, 0, 1), (2, 3, 1, 0), 
(3, 0, 1, 2), (3, 0, 2, 1), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 0, 1), (3, 2, 1, 0). 

コンマと括弧を省略すると次のようになります。

0123 0132 0213 0231 0312 0321
1023 1032 1203 1230 1302 1320
2013 2031 2103 2130 2301 2310
3012 3021 3102 3120 3201 3210

ここから数字 0, 1, 2, 3 をアルファベットの a, b, c, d というものに置き換えます。

abcd abdc acbd acdb adbc adcb
bacd badc bcad bcda bdac bdca
cabd cadb cbad cbda cdab cdba
dabc dacb dbac dbca dcab dcba

実は数字自体には本質的な意味合いはないので、アルファベットに置き換えても構わないのです。これは日本語のひらがなで あ, い, う, え でもいいですし、十干の 甲, 乙, 丙, 丁 でも構いません。あるいは 0, 1, 2, 3 ではなく(各数字を一つずつずらして) 1, 2, 3, 4 でも(むしろ、1, 2, 3, 4 で表現するほうが主流のようです)。順序が付けられていているものでしたらなんでもいいのです。文字コードのかんがえかたに通じますよね。

ここで24個できる全ての順列を辞書式順で並び替えることを考えます。実はすでに辞書式順に並んでいるのですが。辞書式とは英語の辞書に上記24個の単語を掲載するとして、辞書をひく人の簡便を考えて、24個の単語を適切に並び替えたときの順番のことです。

0123 0132 0213 0231 0312 0321
1023 1032 1203 1230 1302 1320
2013 2031 2103 2130 2301 2310
3012 3021 3102 3120 3201 3210

言い換えるならば、一つ前に戻って、上記のように4桁の数字列で順列を表現したものを整数とみなして、大小の順番をつけるときの並べ方です。並び換えの並べ換えということになりますが。

辞書式順に並び替えたものに 0 から順番に整数を割り振ります。

(0, 1, 2, 3) ⇔  0
(0, 1, 3, 2) ⇔  1
(0, 2, 1, 3) ⇔  2
(0, 2, 3, 1) ⇔  3
(0, 3, 1, 2) ⇔  4
(0, 3, 2, 1) ⇔  5
(1, 0, 2, 3) ⇔  6
(1, 0, 3, 2) ⇔  7
(1, 2, 0, 3) ⇔  8
(1, 2, 3, 0) ⇔  9
(1, 3, 0, 2) ⇔ 10
(1, 3, 2, 0) ⇔ 11
(2, 0, 1, 3) ⇔ 12
(2, 0, 3, 1) ⇔ 13
(2, 1, 0, 3) ⇔ 14
(2, 1, 3, 0) ⇔ 15
(2, 3, 0, 1) ⇔ 16
(2, 3, 1, 0) ⇔ 17
(3, 0, 1, 2) ⇔ 18
(3, 0, 2, 1) ⇔ 19
(3, 1, 0, 2) ⇔ 20
(3, 1, 2, 0) ⇔ 21
(3, 2, 0, 1) ⇔ 22
(3, 2, 1, 0) ⇔ 23

一般に  n 個のものからなる順列の全て(総数  n! 個)に対して  0 から  (n!)-1 までの自然数を一対一に対応付けることができます。

例えば、3個の元の並び替えからなる順列の全ては 0 から 5 まで、4個の元の並び替えからなる順列の全ては 0 から 23 まで、5個の元の並び替えからなる順列の全ては 0 から 119 までの自然数と一対一に対応付けられます。

しかし、5個の元の並び替えは120個あることはわかっているけれど、「100 に対応する順列は?」「(3, 1, 0, 2, 4) に対応する自然数は?」と言われるとちょっと答えを出すのに時間がかかりそうです。なにせ、上のような表を120行分書かないといけませんので。

しかも、10個や20個の元の並び替え、あるいはもっと多くの元の並び替えについて上のような問題が与えられても、全ての順列を書くことでそれを求めるには、どれだけ紙があろうと大変な時間がかかります。

とりあえずの目標は『順列と自然数の対応を簡便な方法で計算する』ことにします。これは下記のような問題への対応です。

  •  n 個の元の並び替えの全てを辞書式に並び替えたものに対し、特定の自然数  k (0 \le k < (n!)) 番目に来る順列は?
  • あるいは上の逆で特定の順列に対応する自然数は?