プログラマとプロマネのあいだ

プログラマもやるし、プロマネもやるし、たまに似非アーキとか営業っぽいこともやるITエンジニアがスキルアップの話を中心に日常を綴るブログです。

m個からn個を取り出す順列生成でけた

とりあえずソース。

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)のため、これで終わりです。)

というわけで、多分むちゃくちゃ遅いのですが、一応出来たってことで。