異なるN文字をすべてもってきて,N! 通りの異なる順列がつくれる訳だね.これらの順列ひとつひとつを辞書式順序に従って並べることができる.

<例> 異なる4文字 abcd から作られる異なる順列の数は 4! = 24 通り.それらを以下に並べる(辞書式の順).
  abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda, bdac, bdca, cabd, cadb, cbad, cbda, cdab, cdba, dabc, dacb, dbac, dbca, dcab, dcba

さて,並べずに,いきなり K番目の順列はなにか,と聞かれたら答えられるか.あるいは,逆に,ある順列を見せられたら,それが何番目かはすぐに答えられるか.

上の例だと,たえば,8番目と聞かれたら,すぐに badc だ,と答えられたらOK.また,cbad は何番目? との質問に 15 番目と返事できれば合格.

コンピュータは順列や組合せの計算に非常に苦手.ちょっとでも数字が大きくなるとすぐに天文学的値になって,手に負えなくなる.4文字だけなら24通りすべてを書き出せば答えは判るけど,100文字,1000文字にもなれば,そう簡単に書く出せないだろう.

<順列総数の計算式> 高校数学の復習

  異なるN文字をすべてつかって,作れる異なる順列の総数 = N!

また,N文字のなか,同一文字がm個あるときに,これらのN文字から作れる異なる順列の総数は

  N! / m!

になる.より一般的に言うと,文字 a1 が m1個,文字 a2 が m2個,文字 a3 が m3個...含まれる場合では,

  (同じ文字を含む場合の)異なる順列の総数 = N! / (m1! m2! m3! … )

<例> aabbc から作り出せる順列は以下の通り.
  aabbc, aabcb, aacbb, ababc, abacb, abbac, abbca, abcab, abcba, acabb, acbab, acbba, baabc, baacb, babac, babca, bacab, bacba, bbaac, bbaca, bbcaa, bcaab, bcaba, bcbaa, caabb, cabab, cabba, cbaab, cbaba, cbbaa

総数は30.計算式 5!/(2! 2!) = 30 と合致する.

文字がすべて異なる場合は,上記の計算式の分母にあたる部分はすべて1になるので,同じ文字を含む計算式のほうがより一般的だといえよう.

ということで,本記事の目的は,文字の重複があってもなくても,順列の順番を正しく算出するアルゴリズムを考えることにある.

Comments are closed.

Post Navigation