順列

"abcd" という4文字からなる文字列の文字の現れる順番を変える方法を列記するにはどうすればいいだろうか。この順列が何通りあるかは、4P4 = 4 * 3 * 2 * 1 = 24 通りあるのはすぐ計算できる。問題は、その並べ方を全て見つけるにはどうするかということだ。

高校の数学の教科書を読むと分かるように、まず、先頭の文字を4文字のうちからひとつ取り出す、たとえば'a'を取り出したとしよう。そうすると残りの文字は"bcd"の3種類となる。また、最初の文字の取り出し方は4通りでそれぞれは一致することがないから、全体で4通りの取り出し方がある。

次に2番目の文字について考える。先頭が 'a' の場合についていうと、2番目の文字は "bcd" の3つから選ばないといけないから、その選び方は3通りだ。先頭の文字の選び方が4通りで、そのそれぞれについて3通りの選び方があるから、結局、先頭と2番目の文字の並べ方は 4 * 3 = 12 通りになる。

同様に3番目の文字は1番目2番目が"ab"の場合、"cd" から選ぶと 'c' か 'd' の2通り、"abc" まで選んでしまうと後 'd' しかないのでひと通りになり、結局 "abcd" 4文字の並べ替えは 4 * 3 * 2 * 1 = 24 通りとなることが分かる。

この操作を Haskell でシミュレーションしてみよう。引数に文字列をとり、["abcd", "acbd", ... ] というような文字列のリストを返すような perm xs を定義する。

まず文字列が空文字列の時の perm の戻値は [ [] ] である。[ [] ] とリストの表記になっているが、Haskell では文字列もリストだ。これが perm 関数の初期条件になる。

perm [] = [ [] ]

上の定義は perm "" = [ "" ] と読みかえることができる。つまり空の文字列を perm 関数に与えてやると、空の文字列ひとつだけのリストを戻値として返す。

次に perm にリスト xs を与えたときの再帰的定義を考えてみる。xs から最初の1文字を取り出す方法は、リストの内包的定義 [x | x <- xs ] でできそうだ。また、xs から x 以外の文字列を取り出すには、List モジュールの delete 関数を使って、delete x xs とする。この文字列を perm 関数に与えてやると、

perm (delete x xs)

これは、[ "bcd", "bdc" ] といった、3文字列のリストを返すはずだ。これを最初に取り出した'a'と map 関数で つなげてやると、map (x:) (perm (delete x xs)) -> ["abcd", "acbd", ... ] というリストができるはずだ。したがって、次のような perm 関数の再帰的定義が出来上がる。

perm xs = concat [ map (x:) (perm (delete x xs)) | x <- xs ]

上の定義の concat が不審に思えるが、

[map (x:) (perm (delete x xs)) | x <- xs ] -> [["abcd", "abdc", .. ], ["bacd", "badc", ..] , .. , [ .. ] ] なので、concat で入れ子になったリストを連結する必要があるのだ。

上のプログラムは、List モジュールの delete 関数を使うので、Hugs では :l List としてListモジュールをロードしておく必要がある。下に Hugs で実行した例を示す。

Hugs> :l List
List> perm "abcd" where perm [] = [[]]; perm xs = concat [map (x:) (perm (delete x xs)) | x <- xs]
["abcd","abdc","acbd","acdb","adbc","adcb","bacd","badc","bcad","bcda",
"bdac","bdca","cabd","cadb","cbad","cbda","cdab","cdba","dabc","dacb",
"dbac","dbca","dcab","dcba"]
List>

問題の解決に再帰的手法が使われている例では、Haskell でほとんどそのアルゴリズムのとおりにプログラムすることができる。
[PR]
by tnomura9 | 2011-05-16 13:13 | Haskell | Comments(0)
<< 分類する力 関数の対角線論法 >>