とりあえずソース。
import List main = print $ perm_nm 2 [1,2,3,4] perm :: [Int] -> [[Int]] perm [] = [[]] perm xs = concat $ map perm2 xs where perm2 x = map (x:) $ perm $ delete x xs perm_nm :: Int -> [Int] -> [[Int]] perm_nm n [] = [[]] perm_nm n xs = dellist n $ perm xs where dellist n xxs_permed = if (length $ head $ xxs_permed) == n then xxs_permed else dellist n $ map head $ group $ sort $ concat Map test xxs_permed test xs = [(delete x xs) | x <- xs]
結果はこう。
[[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]]
考え方はこうです。
単純化するために、perm_nm 2 [1,2,3]で例を示します。 (1)とりあえず順列生成する [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] (2)(1)の結果、最初の要素数がnと同じならそのまま返す。そうでなければ次の処理を行う。 (この例では、先頭の要素数が3(/=n)のため、(3)にいきます。) (3)各リストを一次元(?)下げる 例えば、[1,2,3]なら、リストから順番に要素を削ったリストをつなげて、[[2,3],[1,3],[1,2]]とする。 これを全要素に対してやると、 [[[2,3],[1,3],[1,2]],[[3,2],[1,2],[1,3]],[[1,3],[2,3],[2,1]],[[3,1],[2,1],[2,3]],[[1,2],[3,2],[3,1]],[[2,1],[3,1],[3,2]]] となります。 (4)(3)に対して、concatすると、 [[2,3],[1,3],[1,2],[3,2],[1,2],[1,3],[1,3],[2,3],[2,1],[3,1],[2,1],[2,3],[1,2],[3,2],[3,1],[2,1],[3,1],[3,2]] となります。 (5)(4)で重複要素を削除するため、sortしてgroupしてmap headします。 [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]] (6)(5)の結果をもって、(2)へ戻ります。 (この例では、先頭の要素数が2(==n)のため、これで終わりです。)
というわけで、多分むちゃくちゃ遅いのですが、一応出来たってことで。