辞書式配列

数学玉手箱
URL http://izumi-math.jp/sanae/
E-mail [email protected]
辞書式配列
単語または文の中の文字をいくつか入れ替えることによって全く別の意味にさせることをアナグラ
ム（anagram）といいますね。文字列を逆順にして一致するかどうかを調べればよい回文とは異なり、
異なる n 種類の文字列なら n! の並べ替えが可能となります。有名人では、タモリが本名の苗字（森田）
のアナグラムになっています。
さて、高校で習う順列の問題で代表的な「辞書式配列」について考えてみましょう。「辞書式配列」
とは、n 個の文字 A, B, C, D, E, F, ・・・の全てを用いて作られる文字列(単語)を ABCDEF・・・からア
ルファベット順に並べることをいいます。
【例題】 5 個の文字 A, B, C, D, E の全てを用いて作られる文字列を ABCDEF からアルファベット
順に並べる。次の問いに答えよ。
(1) 63 番目の文字列は何か。
(2) DBEAC は最初から数えて何番目にあるか。
（解答）(1) A○○○○ の形の文字列は
4! = 24 （個）
B○○○○ の形の文字列は
4! = 24 （個）
CA○○○ の形の文字列は
3! = 6 （個）
CB○○○ の形の文字列は
3! = 6 （個）
ここまでの合計は
24 + 24 + 6 + 6 = 60 （個）
よって，63 番目の文字列は，CD○○○ の形の文字列の 3 番目である。
順に書き出すと CDABE，CDAEB，CDBAE，…… であるから，求める文字列は CDBAE
(2) DBEAC の前に並んでいる文字列のうち，A○○○○，B○○○○，C○○○○ の形のものは全部
で
4!×3 = 72 (個)
DA○○○ の形のものは
3! = 6 （個）
DBA○○，DBC○○ の形のものは全部で
2!×2 = 4 （個）
よって，DBEAC は
72 + 6 + 4 + 1 = 83 （番目）■
案外面倒なことがわかります。これをもっとユークリッドの互除法のような方法で、簡単に求めてみ
ましょう。まず (1) 63 番目の文字列を求めてみます。p = 63, n = 5（文字）とします。p を (n - 1)! で割
った商をα1、余りをβ1 とします。つまり、63 = 2×4! + 15 なので、α1= 2, β1= 15 となります。出て
きた余りを (n - 2)! で割った商をα2、余りをβ2 とし、これを繰り返します。すると、
63 = 2×4! + 15
α1= 2, β1= 15
15 = 2×3! + 3
α2= 2, β2= 3
3 = 1×2! + 1
α3= 1, β3= 1
2 63
1 = 1×1! + 0
α4= 1, β4= 0
このαの値は右の図のように簡単に求めることができます。
3 31 …1
63 = 2×31 + 1 = 2×( 3×10 + 1) + 1
4 10 …1
= 2×3×10 + 1×2×3 + 1
= 2×3×( 4×2 + 2) + 1×2×3 + 1
2 …2
= 2×3×4×2 +2×3×2 + 1×2×3 + 1
= 2×4! +2×3! + 1×2! + 1×1!
さて本題に戻ります。63 番目の文字列を求めるため、次のようなアルゴリズムを考えます。
①
②
③
④
p = n! のときは、文字列を反対に並べたもの。そうでないときは、
アルファベット順の 1 番目の文字列を縦に書く
文字列 α+ 1 番目にチェック(◯)を入れる。
チェックした文字以外の文字列を、右側に縦に書く。
⑤ ③④をβ ≠ 0 の間続ける。
⑥ β = 0 のとき、α 番目にチェックを入れ、文字列が残っている場合は、アルファベット順の最後
の文字列を書く。
p = 63 のときは、右図のようになります。そして、チェッ
2
ク（◯）のついた文字を左から追っていくと求める文字列が
得られます。つまり答えは CDBAE となります。
反対の操作で (2) DBEAC は最初から数えて何番目にあ
るか、を求めてみましょう。アルゴリズムは次のように逆に
なります。
① アルファベット順の 1 番目の文字列を縦に書く。
② 文字列の文字を左から順位チェック（○）を入れる。
③ チェックを入れた文字列の上にある文字数をαとし、チ
ェックを入れた文字以外の文字数を n とし、α×n! を 3
計算する。
④ ②③を繰り返す。文字列の最後の文字のときは 1 を加え
る。
これを用いると、p = 3×4! +1×3! + 2×2! + 0×1! + 1 = 83
（番目）となります。
A
B
C
D
E
A
B
C
D
E
2
1
A
B
D
E
A
B
C
E
1
2
A
B
E
A
C
E
0
0
A
E
E
A
C
+1
C
では、このやり方で次の問題をやってみよう。
【問題】 5 個の文字 A, B, C, D, E の全てを用いて作られる文字列を ABCDEF からアルファベット
順に並べる。次の問いに答えよ。
(1) 40 番目の文字列は何か。
(2) CBEDA は最初から数えて何番目にあるか。
(1)
2
3
4
40 = 1×4! + 16
α1= 1, β1= 16
16 = 2×3! + 4
α2= 2, β2= 4
4 = 2×2! + 0
α3= 2, β3= 0
下図より BDCEA
(2) 下図より
2×4! +1×3! + 2×2! + 1×1! + 1 = 60 （番目）
1
A
B
C
D
E
2
A
B
D
E
2
1
A
C
E
0
A
E
A
A
B
C
D
E
1
A
B
D
E
2
A
D
E
1
A
D
40
20
6
1
+1
A
…0
…2
…2

Download Report