Haskellで順列 - KimuraShinichi’s blog

　順列というのは、要素の順番を区別するような、ひとそろえの並べ方。
　リストを渡すと、その要素を並べ替えた結果(リスト)のリストを返す関数にしてみます。

　ある長さのリストの順列を作るには、すべての場合をもれなく考えないといけない。
　いきなりすべての場合をもれなく考えるのはむずかしい。
　これは、なかなかたいへん。だけど、数学的帰納法っていう便利な考え方がある。
　ひとつぶんだけ短いリストの順列ができあがっていれば、なんとか考えられないか。もしそれができれば、そのひとつ前、そのまたひとつ前とさかのぼっていけば、要素がたったひとつの場合か、または0個の場合にたどり着く。
　要素がひとつだけなら、並べ方はひととおりしかない。
　要素が0個なら、並べ方も0個しかない。

　できあがっている短い順列のどれでもいいからどれかひとつを取り出してみよう。
　これに、もうひとつだけ新しい要素を追加するすべての仕方は？

　もうひとつだけ追加するのだったら、新しい要素の追加の仕方は、リストの直前(0の位置)に置くか、先頭要素の次(1の位置)に置くか、リストの要素のどこかの中間(2,...(n-1)の位置)に置くか、リストの直後(nの位置)に置くか。
　そのどれかでしかない。

　ひとつぶんだけ短いリストのそれぞれについて、同じことができるから、リストの長さnからひとつずつ減らしていって0になるまで続ければ全部になる。

　あら、できた。

permutation [] = []
permutation [a] = [[a]]
permutation (a:as) = mix (length as) a (permutation as)
  where
    mix 0 x ys = map (insert 0 x) ys
    mix n x ys = mix (n-1) x ys ++ map (insert n x) ys
    insert n x ys = (take n ys) ++ [x] ++ (drop n ys)

　実行してみる。1から4までのリストで試すと：

Main> permutation [1..4]
[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,4,2,3],[1,3,4,2],[1,4,3,2],[2,1,3,4],[2,1,4,3]
,[3,1,2,4],[4,1,2,3],[3,1,4,2],[4,1,3,2],[2,3,1,4],[2,4,1,3],[3,2,1,4],[4,2,1,3]
,[3,4,1,2],[4,3,1,2],[2,3,4,1],[2,4,3,1],[3,2,4,1],[4,2,3,1],[3,4,2,1],[4,3,2,1]
]

　でもねえ。
　permutation [1..140] くらいで、

ERROR - C stack overflow

となってしまいました。

　permutation [1..140] では、

ERROR - Garbage collection fails to reclaim sufficient space

になります。

　ふむう。
　間違ってるわけではなさそうだけど、もうちょっと工夫しないとだめかな。