なんとなく覚え書き的に.
とりあえず順列.
import Data.List (delete) perms [] = [[]] perms xs = [ h:t | h <- xs, t <- perms (delete h xs) ]
perms は, 引数に与えられたリストが空ならば空のリストをだだ一つ持つリストを返す.
引数に与えられたリストが空でないなら, そのリストを xs とする.
xs から順番に要素を取り出し, これを h とする.
xs から h を (あれば) 削除したリストに対して perms を呼び出した結果の各要素を順番に取り出し t とする.
t の先頭に h を付加したもののリストが結果である.
要素三つの場合で評価がどんな風に行われるか手で書いて確認してみます.
perms [2, 3, 5] = [ h:t | h <- [2,3,5], t <- perms (delete h xs) ]
= [[2:t | t <- perms (delete 2 [2,3,5]) ],
[3:t | t <- perms (delete 3 [2,3,5]) ],
[5:t | t <- perms (delete 5 [2,3,5]) ]]
= [[2:t | t <- perms [3,5]],
[3:t | t <- perms [2,5]],
[5:t | t <- perms [2,3]]]
ところで,
perms [3,5] = [ h:t | h <- [3,5], t <- perms (delete h xs) ] = [[3:t | t <- perms (delete 3 [3,5])], [5:t | t <- perms (delete 5 [3,5])]] = [[3:t | t <- perms 5], [5:t | t <- perms [3]]]
ところで
perms [3] = [3:t | t <- perms (delete 3 [3])] = [3:t | t <- perms []] = [3:[]] = [[3]]
perms [] は [[]] すなわち空のリストをただ一つ含むリストですから, その全ての要素を順に t に代入するということは, t が空のリストの場合だけです. 空リスト [] の先頭に 3 を追加した結果は 3 だけを要素とするリストです.
同様に perms [5] = [[5]] です.
perms [3,5] の評価の続き,
= [[3:t | t <- perms 5], [5:t | t <- perms [3]]] = [3:[5], 5:[3]] = [[3,5], [5,3]]
同様に
perms [2,5] = [[2,5], [5,2]] perms [2,3] = [[2,3], [3,2]]
です.
perms [2,3,5] の評価に戻ると
= [[2:t | t <- perms [3,5]], [3:t | t <- perms [2,5]], [5:t | t <- perms [2,3]]] = [2:[3,5], 2:[5,3], 3:[2,5], 3:[5,2], 5:[2,3], 5:[3,2]] = [[2,3,5], [2,5,3], [3,2,5], [3,5,2], [5,2,3], [5,3,2]]
ghci で :l して動作確認.
*Main> perms "abcd" ["abcd","abdc","acbd","acdb","adbc","adcb","bacd","badc","bcad","bcda","bdac","bdc a","cabd","cadb","cbad","cbda","cdab","cdba","dabc","dacb","dbac","dbca","dcab","d cba"] *Main> perms [2, 3, 5, 7] [[2,3,5,7],[2,3,7,5],[2,5,3,7],[2,5,7,3],[2,7,3,5],[2,7,5,3],[3,2,5,7],[3,2,7,5],[ 3,5,2,7],[3,5,7,2],[3,7,2,5],[3,7,5,2],[5,2,3,7],[5,2,7,3],[5,3,2,7],[5,3,7,2],[5, 7,2,3],[5,7,3,2],[7,2,3,5],[7,2,5,3],[7,3,2,5],[7,3,5,2],[7,5,2,3],[7,5,3,2]]
いいですね.
数値に対して数値のリストで返したいので
*Main> map (read::String->Int) $ perms $ show 23579 [23579,23597,23759,23795,23957,23975,25379,25397,25739,25793,25937,25973,27359,273 95,27539,27593,27935,27953,29357,29375,29537,29573,29735,29753,32579,32597,32759,3 2795,32957,32975,35279,35297,35729,35792,35927,35972,37259,37295,37529,37592,37925 ,37952,39257,39275,39527,39572,39725,39752,52379,52397,52739,52793,52937,52973,532 79,53297,53729,53792,53927,53972,57239,57293,57329,57392,57923,57932,59237,59273,5 9327,59372,59723,59732,72359,72395,72539,72593,72935,72953,73259,73295,73529,73592 ,73925,73952,75239,75293,75329,75392,75923,75932,79235,79253,79325,79352,79523,795 32,92357,92375,92537,92573,92735,92753,93257,93275,93527,93572,93725,93752,95237,9 5273,95327,95372,95723,95732,97235,97253,97325,97352,97523,97532]
show で文字列 (文字のリスト) に変換, perms で文字を並べ替えた文字列のリストにして, (read::String->Int) で文字列から Int に変換する操作を map で全ての要素に適用.
追記:
「Haskell 順列」で検索するといろいろ出てくる.
import Data.List perms [] = [[]] perms xs = concat [ map (x:) $ perms (delete x xs) | x <- xs]
の方が変数一個少ない.
追記2:
Data.List に permutations が既定義だった…
Prelude> :module Data.List Prelude Data.List> permutations [2,3,5] [[2,3,5],[3,2,5],[5,3,2],[3,5,2],[5,2,3],[2,5,3]]
辞書順にならないらしい.