順列というのは対象を順番に並べるときの並べ方である。例えば、3124は 1,2,3,4の数字の順列の一つである。全ての順列が数字またはアルファベット順 に並んでいるとき、それを辞書式順序と呼ぶ。0,1,2の辞書式順列は012 021 102 120 201 210となる。
0,1,2,3,4,5,6,7,8,9の数字で作った順列の100万番目を求めよ。
与えられたリストの要素を順番に使って全ての順列のリストを返す関数 permutationを考える。順列は要素のリストとする。要素が一つしかないとき、 そのリストが全ての順列のリストとなる。
要素が複数あるときは、その中のひとつが一番最初にくると考えたとき、後ろ に続く順列は残りの要素の順列として再帰的に順列が定義できる。具体的には ここではmapを用いて、全ての要素がそれぞれ先頭だった場合について、 deleteで残りの要素を求め、permutationを再帰的に適用することで残りの部分 の順列を求めている。そして求まった順列に最初に取り除いた要素を付け加え ることで順列を求めている。この結果は先頭要素ごとの順列のリストになるの で、最後にconcatを使ってひとつのリストにする。
求める答えは0から9までの順列の1000000番目である。リストのインデックスは 0から始まるので999999を取り出せば答えとなる。前から順番に要素を使って順 列を生成していく場合、ソートしなくても結果は順番に並んでいる。
permutation [a] = [[a]] permutation l = concat $ map (\x -> map (x :) $ permutation $ delete x l) l euler024 = permutation [0..9] !! 999999