辞書式順列とは　考え方と解法

 

---

 

 

辞書式順列とは

辞書式順列とはなんでしょうか。普通の順列とは違うらしいです。何が違うのでしょう。

ところで、皆さん辞書は手元にありますか。もしあれば開きながらこの記事を読むと良いでしょう。最近は電子辞書やウェブの発達で言葉を入れればすぐにその言葉の意味を探してくれるという便利な時代になりました。

ただそれでは辞書式という意味がわからなくなってしまうので一冊は辞書を持っておくと良いでしょう。英和でも、数学辞典でも広辞苑でも。

少し脇道に逸れましたので戻ってきます。辞書式とは辞書を見れば一発ですが

 

頭文字から順番に 「A」 から 「Z」 又は 「あ」 から「ん」 までを考え、若い文字(最初の文字)から順番に文字列を作る方法

 

です。言葉だとなんとも歯がゆい感じになってしまうので例を挙げながら考えていきます。

例えば英単語を考えましょう。この2つの単語は辞書式で考えるとどちらが先に来ますか。

 

run ran

 

辞書式によると頭文字から順番にその単語のアルファベットを考え、a に近い方が先に出てきます。

今回の場合、どちらの単語も頭文字は「r」で変わりませんが、次のアルファベットは「u」と「a」なので、この時点で辞書式では

 

ran run

 

の順になります。大丈夫ですか？ではこれに加えて「rain」と「rush」という単語も入れてみます。辞書式だとどんな順番になりますか。

 

答えは

rain ran run rush

 

ですね。２文字目まで文字列が同じの時は３文字目を見ましょう。「rain」と「ran」だと「i」と「n」を比べることになりますが、もちろん 「i」の方が先です。同じ理由で「run」と「rush」も「n」と「s」を比べることになりますので「run」が先ですね。

こんな風に並べていくものを辞書式と言います。なんとなくイメージはつかめましたか？

いったん広告の時間です。

辞書式に並べる問題

順列の問題で出てくるのは次のような問題です。

 

 

 

 

順列の問題ではアルファベットなどの文字列を辞書式に並べていき、特定の文字列が何番目に出てくるかをよく聞かれます。

この問題がなぜ順列で考えられるかを見ていきましょう。今回の問題で一番最初に出てくる文字列は

 

ABCD

 

ですね。ではその次はなんでしょう。これがわかれば辞書式がわかっている証拠です。答えは

 

ABDC

 

ですね。頭文字からずっと同じで最後の2文字が変われば、考えられる文字列の中で2番目にくるでしょう。

ではその次は。同じように考えると、最初の文字は変わる余地がありません。先ほどは最後の2文字でしたが、次は

 

ACBD

 

とすれば辞書式で次にくる文字列です。こうすると

 

ABCD

ABDC

ACBD

ACDB

・・・

 

のようにどんどんと考えることができます。では今回の問題にある

 

DACB

 

は一体辞書式で何番目の文字列なんでしょうか。

もちろん全ての並べ方は膨大なので書き下すことはしません。日が暮れてしまいます。

ではどうするか。書き下すことはしないにしても特定の頭文字の文字列が何パターンがあるかは考えることができそうです。

どういうことかというと、例えば頭文字が A の文字列は必ず頭文字が B の文字列よりも辞書式的に先に来ます。

ですから A が頭文字の文字列のパターンは

 

 

と考えることができます。後ろの文字が何であっても頭文字が B の文字列よりも「辞書式的に後」ですよね。

つまり辞書式では

 

 

のようにその中身は詳細にわからないにしてもこんな風に文字列が並んでいくという検討がつけられます。

そしてここで順列を使うのです。頭文字が A の文字列は後ろの並び替え分だけパターンがあるので

 

\(3!=3\cdot 2\cdot 1=6\) 通り

 

と計算すれば頭文字が A のパターンが６通りあることがわかります。ということは

 

 

のように少しずつどの文字列が何番目にあるのかが見えてくるわけです。これを使うと文字列 DACB が何番目にくるかを求めることができます。

実際にやってみましょう。まず頭文字はDなのでその頭文字よりも最初にある文字列を数え上げてしまいます。

つまり先ほどやったように

 

頭文字がAである文字列は\(3!=3\cdot 2\cdot 1=6\) 通り

頭文字がBである文字列も\(3!=3\cdot 2\cdot 1=6\) 通り

頭文字がCである文字列も\(3!=3\cdot 2\cdot 1=6\) 通り

 

ですね。あとは頭文字がDの文字列を辞書式に考えれば良さそうです。

頭文字がDの文字列を辞書式に並べると、

 

DABC

DACB

DBAC

DBCA

・・・

 

ですから欲しい文字列は 番目ですね。以上から結局文字列 は

 

20番目

 

であることがわかりました。順列をうまく使えましたか？同じように(2)の問題もやってみましょう。

これもすぐできます。先ほど

 

頭文字がAである文字列は\(3!=3\cdot 2\cdot 1=6\) 通り

頭文字がBである文字列も\(3!=3\cdot 2\cdot 1=6\) 通り

頭文字がCである文字列も\(3!=3\cdot 2\cdot 1=6\) 通り

 

と分かったので、15番目の文字列は頭文字が C の文字列のどれかですね。12番目までは頭文字が A,B の文字列で、頭文字が D まで行くと19番目まで行ってしまいますから。

というわけでここまでくればあとは地道にやった方が速そうです。頭文字が C の文字列を辞書式に並べると

 

CABD

CADB

CBAD

CBDA

・・・

 

ですから、15番目は

 

CBAD

 

ですね。めでたしです。

まとめ