2016年10月19日水曜日

順列のアルゴリズム

という3個の要素を持つリストから2個取り出す順列()は

の6通りある。

これを先頭要素であるを含んでいると、を含まないに分けて考えてみる。

まずを含む方からを除いてみると、となる。このは、から先頭要素を取り除いた残りのから一つを取り出すときの順列である。そして、の先頭に挿入したものであり、また、の右隣りに挿入したものとなっていることがわかる。も同様である。このことから、の結果には、先頭要素を取り除いた残りのリストから個を取り出す順列の結果のそれぞれに、取り除いておいた元のリストの先頭要素を左から順に位置を変えて挿入したものが含まれているといえる。

次に、を含まない方を見てみると、は、から2つを取り出すときの順列となっている。

これを関数(第一引数として挿入する値、第二引数としてリストを取り、値を左から順に異なる位置に挿入したリストのリストを返す。関数(渡された関数をリストの各要素に適用した結果をリストにまとめる関数)を使って式に表してみると以下のようになる関数はリストのリストを返すので、それをした結果はリストのリストを要素として持つリストになる。そのため実際のコードを書くときには、一番外側のリスト減らすためにconcat関数を適用する必要があるが、ここでは見やすさのために省略してある。最後の方にHaskellで書いたコードにはconcat関数を使ってある)

を結果のリストに置き換えると

となる。

これを一般化してみる。

はリストの先頭要素

この式を基にして、n個の要素を持つリストで考えた場合、(n個からr個取り出す順列)を求めるアルゴリズムを文章化すると次のようになる。

  1. 先頭要素を除いた個のリストから個を取り出す順列を作る。そして、それぞれの結果に対して最初に取り除いておいた元のリストの先頭要素を挿入する。
  2. 次に、先頭要素を除いた個のリストから、今度は個を取り出す順列を作る。の場合とは異なり、この結果には取り除いておいた先頭要素は挿入しない。
  3. のリストとのリストをつなぎあわせたリストが最終的な結果となる

手順およびはそれぞれ再帰処理となるが、その際の場合分けは次の通り。

  • が空リストのときは空リストを返す。
  • のときは選び方は通りあるので、引数として受け取ったリストの各要素をそれぞれリストにして、ネストしたリストを返す。(例: ならにして返す)

これをHaskellで書くとこうなる。

-- 引数nはリスト ex:[1,2,3,4,5]
-- 引数rはnから取り出す要素数

nPr :: [a] -> Int -> [[a]]
nPr [] _ = []
nPr n 1 = map (:[]) n
nPr (x:xs) r = (concat $ map (insertion x) $ nPr xs $ r - 1) ++ (nPr xs r)

insertion :: a -> [a] -> [[a]] 
insertion x xs = [insertion' x xs n | n <- [0..(length xs)]]

insertion' :: a -> [a] -> Int -> [a]
insertion' x xs n = take n xs ++ [x] ++ drop n xs

ghciで5個から3個を取り出す順列を求める

ghci> nPr [1..5] 3
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1],[1,2,4],[2,1,4],[2,4,1],[1,4,2],[4,1,2],[4,2,1],[1,2,5],[2,1,5],[2,5,1],[1,5,2],[5,1,2],[5,2,1],[1,3,4],[3,1,4],[3,4,1],[1,4,3],[4,1,3],[4,3,1],[1,3,5],[3,1,5],[3,5,1],[1,5,3],[5,1,3],[5,3,1],[1,4,5],[4,1,5],[4,5,1],[1,5,4],[5,1,4],[5,4,1],[2,3,4],[3,2,4],[3,4,2],[2,4,3],[4,2,3],[4,3,2],[2,3,5],[3,2,5],[3,5,2],[2,5,3],[5,2,3],[5,3,2],[2,4,5],[4,2,5],[4,5,2],[2,5,4],[5,2,4],[5,4,2],[3,4,5],[4,3,5],[4,5,3],[3,5,4],[5,3,4],[5,4,3]]

length関数で何通りあるか数える

ghci> length $ nPr [1..5] 3
ghci> 60

順列の公式: で答えが合っているか調べる

ghci> (product [1..5]) `div` (product [1..2]) 
ghci> 60

0 件のコメント:

コメントを投稿