今回は簡単な例題として、「順列 (permutation)」と「組み合わせ (combination)」を取り上げます。Haskell のモジュール Data.List には順列を生成する関数 permutations が用意されていますが、私たちでも簡単にプログラムすることができます。
異なる n 個の順列の総数は、n の階乗 (n!) だけあります。たとえば、3 つの整数 1, 2, 3 の順列は次に示すように 6 通りあります。
1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1
順列を生成するプログラムは再帰定義で簡単に作ることができます。[1, 2, 3] の順列を生成する場合、最初に 1 で始まる順列を生成します。これは 1 を取り除いた数字 [2, 3] の順列を生成することで実現できます。次は 2 で始まる順列を生成します。同様に、2 を取り除いた数字 [1, 3] の順列を生成すればいいわけです。[2, 3] や [1, 3] の順列を生成する場合も同じように考えることができます。
それではプログラムを作りましょう。最初に、リストから要素を一つ選んで、選んだ要素と残りの要素を返す関数 select を作ります。次のリストを見てください。
リスト : 要素の選択 select :: [a] -> [(a, [a])] select [x] = [(x, [])] select (x:xs) = (x, xs) : map (\(y, ys) -> (y, x:ys)) (select xs) -- 別解 select' :: [a] -> [(a, [a])] select' [x] = [(x, [])] select' (x:xs) = (x,xs) : [(y, x:ys) | (y, ys) <- select' xs]
select は選んだ要素と残りの要素をタプルに格納し、それをリストに格納して返します。最初の節で、リストの要素が一つしかない場合は (x, []) をリストに格納して返します。これが再帰呼び出しの停止条件です。
次の節で、リストを x : xs で分解します。先頭要素 x を選ぶ場合は (x, xs) をリストに格納するだけです。それ以外の場合は、xs に対して select を再帰呼び出しし、返り値のタプルの第 2 要素 ys (残りの要素を格納したリスト) に x を追加します。この処理は map を使うと簡単ですね。あとは、map の返り値に (x, xs) を追加するだけです。別解はリスト内包表記でプログラムしたものです。
それでは実行してみましょう。
ghci> select [1,2,3] [(1,[2,3]),(2,[1,3]),(3,[1,2])] ghci> select [1,2,3,4] [(1,[2,3,4]),(2,[1,3,4]),(3,[1,2,4]),(4,[1,2,3])] ghci> select [1,2,3,4,5] [(1,[2,3,4,5]),(2,[1,3,4,5]),(3,[1,2,4,5]),(4,[1,2,3,5]),(5,[1,2,3,4])]
select を使うと順列を生成する関数 permutations は簡単にプログラムすることができます。
リスト : 順列の生成 permutations :: [a] -> [[a]] permutations [] = [[]] permutations xs = concatMap (\(y, ys) -> map (y:) (permutations ys)) $ select xs -- 別解 permutations' :: [a] -> [[a]] permutations' [] = [[]] permutations' xs = [y:zs | (y, ys) <- select xs, zs <- permutations' ys]
関数 permutations は引数のリスト xs から順列を生成し、それをリストに格納して返します。引数が空リストになるときが再帰の停止条件で、空リストを格納したリストを返します。このリストに対して要素を追加していきます。この処理は map を二重に使うと簡単に実現できそうです。次の例を見てください。
ghci> map (5:) [[1],[2],[3],[4],[5]] [[5,1],[5,2],[5,3],[5,4],[5,5]] ghci> map (\y -> map (y:) [[1],[2],[3],[4],[5]]) [5,6] [[[5,1],[5,2],[5,3],[5,4],[5,5]],[[6,1],[6,2],[6,3],[6,4],[6,5]]]
リストの各要素に 5 を追加したい場合、map を使うと簡単ですね。次は、リスト [5, 6] の各要素を追加したリストを求めることを考えます。map を二重にして、[5, 6] の要素をラムダ式の引数 y に渡します。次の map で y をリストに追加します。すると、返り値のリストには 5 を追加したリストと 6 を追加したリストが格納されます。map を二重にしているので、リストの階層が一段深くなるわけです。
そこで、リストを一段階だけ平坦化することにします。Haskell には concat という関数が用意されています。簡単な例を示しましょう。
ghci> :t concat concat :: [[a]] -> [a] ghci> concat [[1,2,3],[4,5,6],[7,8,9]] [1,2,3,4,5,6,7,8,9]
実際のプログラムでは平坦化と map を組み合わせた関数を定義しておくと便利です。Haskell には関数 concatMap が用意されています。簡単な使用例を示しましょう。
ghci> :t concatMap concatMap :: (a -> [b]) -> [a] -> [b] ghci> concatMap (\y -> map (y:) [[1],[2],[3],[4],[5]]) [5,6] [[5,1],[5,2],[5,3],[5,4],[5,5],[6,1],[6,2],[6,3],[6,4],[6,5]]
ご参考までに、concatMap のプログラムを示します。
リスト : concatMap concatMap :: (a -> [b]) -> [a] -> [b] concatMap _ [] = [] concatMap f (x:xs) = f x ++ concatMap f xs
関数 permutations の説明に戻ります。ラムダ式の中で permutations を再帰呼び出しをして、リスト ys の順列を生成します。そして、その返り値に選択した要素 y を追加すれば順列を生成することができます。別解はリスト内包表記でプログラムしたものです。
簡単な実行例を示しましょう。
ghci> permutations [1,2,3] [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ghci> permutations [1,2,3,4] [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],[2,1,4,3], [2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],[3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1], [3,4,1,2],[3,4,2,1],[4,1,2,3],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]]
なお、permutations で生成されるリストは「遅延ストリーム」として利用することもできます。たとえば、[1,2,3,4] の順列の総数は 24 通りありますが、take 1 $ permutations [1,2,3,4] とすると、[1,2,3,4] が取り出されますが、残りの順列はまだ生成されていません。必要になった時点で順列が生成されます。
もうひとつ別解を示しましょう。
リスト : 別解 (2) permutations'' :: [a] -> [[a]] permutations'' xs = perm xs [] [] where perm [] ys zs = reverse ys : zs perm xs ys zs = foldr (\(x, xs) a -> perm xs (x:ys) a) zs $ select xs
局所関数 perm は、第 2 引数のリストに要素を追加していき、完成した順列を第 3 引数のリストに格納します。最初の節で、第 1 引数が空リストになったら順列が一つ完成しました。reverse で ys を反転してから zs に追加して返します。perm を呼び出す場合、この返り値を第 3 引数に渡すことで、生成した順列を格納していくことができます。
次の節で、foldr の初期値を第 3 引数の zs にすることで、ラムダ式の引数 a に順列を格納するリストを渡します。あとは perm を再帰呼び出しすると、その返り値は次にラムダ式を呼び出すときの引数 a に渡されるので、順列を格納したリストを perm に渡していくことができます。
それでは実行結果を示します。
ghci> permutations'' [1..4] [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],[2,1,4,3], [2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],[3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1], [3,4,1,2],[3,4,2,1],[4,1,2,3],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]]
リストの要素に型クラス制約 Eq を付けると、select を使わないでプログラムを作ることができます。次のリストを見てください。
リスト : 順列の生成 (2) permutations :: Eq a => [a] -> [[a]] permutations [] = [[]] permutations xs = concatMap (\x -> map (x:) (permutations (filter (/=x) xs))) xs -- 別解 permutations' :: Eq a => [a] -> [[a]] permutations' [] = [[]] permutations' xs = [x:ys | x <- xs, ys <- permutations' (filter (/=x) xs)]
要素の選択は concatMap で行います。この場合、先頭の要素から順番に選択することになります。そして、permutations を再帰呼び出しするとき、リスト xs から選んだ要素 x を filter で削除します。これで x を取り除いたリストの順列を生成することができます。あとは、返り値の要素 (リスト) の先頭に x を追加していくだけです。別解はリスト内包表記でプログラムしたものです。
リストから n 個の要素を選んで順列を生成することも簡単にできます。次のリストを見てください。
リスト : n 個の要素を選んで順列を生成する permutation :: Int -> [a] -> [[a]] permutation 0 _ = [[]] permutation n xs = concatMap (\(y, ys) -> map (y:) (permutation (n - 1) ys)) $ select xs -- 別解 permutation' :: Int -> [a] -> [[a]] permutation' 0 _ = [[]] permutation' n xs = [y:zs | (y, ys) <- select xs, zs <- permutation' (n - 1) ys]
関数名は permutation としました。最初の引数が選ぶ要素の個数を表します。0 ならば [[ ]] を返します。これが再帰呼び出しの停止条件です。あとは、perumtation を再帰呼び出しするとき個数を -1 するだけです。別解はリスト内包表記でプログラムしたものです。
それでは実行してみましょう。
ghci> permutation 3 [1,2,3,4] [[1,2,3],[1,2,4],[1,3,2],[1,3,4],[1,4,2],[1,4,3],[2,1,3],[2,1,4],[2,3,1],[2,3,4] ,[2,4,1],[2,4,3],[3,1,2],[3,1,4],[3,2,1],[3,2,4],[3,4,1],[3,4,2],[4,1,2],[4,1,3] ,[4,2,1],[4,2,3],[4,3,1],[4,3,2]]
型クラス制約 Eq を付ける場合も同様にプログラムすることができます。
次は「組み合わせ (combination)」を生成するプログラムを作ってみましょう。たとえば、リスト [1, 2, 3, 4, 5] の中から 3 個を選ぶ組み合わせは次のようになります。
1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5 2 3 4, 2 3 5, 2 4 5, 3 4 5
最初に 1 を選択した場合、次は [2, 3, 4, 5] の中から 2 個を選べばいいですね。2 番目に 2 を選択したら、次は [3, 4, 5] の中から 1 個を選べばいいわけです。これで、[1, 2, 3], [1, 2, 4], [1, 2, 5] が生成されます。[2, 3, 4, 5] の中から 2 個選ぶとき、2 を選ばない場合があります。この場合は [3, 4, 5] の中から 2 個を選べばいいわけです。ここで 3 を選ぶと [1, 3, 4], [1, 3, 5] が生成できます。同様に、3 を除いた [4, 5] の中から 2 個をえらぶと [1, 4, 5] を生成することができます。
これで 1 を含む組み合わせを生成したので、次は 1 を含まない組み合わせ、つまり [2, 3, 4, 5] から 3 個を選ぶ組み合わせを生成すればいいわけです。けっきょく、この処理の考え方は次に示す組み合わせの公式と同じです。
これをプログラムすると次のようになります。
リスト : 組み合わせの生成
combinations :: Int -> [a] -> [[a]]
combinations n xs = comb n (length xs) xs where
comb 0 _ _ = [[]]
comb r n a@(x:xs)
| n == r = [a]
| otherwise = map (x:) (comb (r - 1) (n - 1) xs) ++ comb r (n - 1) xs
実際の処理は局所関数 comb で行います。第 1 引数が選ぶ個数 r、第 2 要素が要素の個数 n、第 3 引数が要素を格納したリストです。最初の節は r が 0 の場合です。選択する要素がないので空リストを格納したリストを返します。最後の節で、n と r が等しい場合は、その要素を全て選択するのでリスト [a] を返します。
そうでなければ、先頭要素 x を選びます。残りのリスト xs から r - 1 個を選ぶ組み合わせを生成して、その先頭に x を追加します。あとは、xs から r 個を選ぶ組み合わせを comb で求めて、演算子 ++ で連結するだけです。
それでは実行してみましょう。
ghci> combinations 2 [1,2,3,4,5] [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]] ghci> combinations 3 [1,2,3,4,5] [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]] ghci> combinations 4 [1,2,3,4,5] [[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5]]
正常に動作していますね。
ところで、参考 URL "Haskell-jp wiki" には、もっと簡潔なプログラムが掲載されています。参考 URL "Haskell-jp wiki" よりプログラムを引用します。
リスト : 組み合わせの生成 (引用) comb :: [a] -> Int -> [[a]] comb _ 0 = [[]] comb [] _ = [] comb (x:xs) n = map (x:) (comb xs (n-1)) ++ comb xs n
引数のリストが空リストになったら、組み合わせを生成できないので空リストを返すところがポイントです。xs ++ [ ] や [ ] ++ xs は xs になるので、空リストを返しても正常に動作するわけです。とても参考になりました。山下伸夫さんに感謝いたします。
演算子 ++ を使わない場合は次のようになります。
リスト : 別解 combinations' :: Int -> [a] -> [[a]] combinations' n xs = comb n xs [] [] where comb 0 _ ys zs = reverse ys : zs comb _ [] _ zs = zs comb n (x:xs) ys zs = comb (n - 1) xs (x:ys) (comb n xs ys zs)
局所関数 comb は、第 3 引数のリストに要素を追加していき、生成した組み合わせを第 4 引数のリストに格納します。最初の節で、第 1 引数が 0 になったら組み合わせが一つ完成しました。reverse で ys を反転してから zs に追加して返します。comb を呼び出す場合、この返り値を第 3 引数に渡すことで、生成した順列を格納していくことができます。
次の節で、リストが空リストになったら組み合わせを生成できないので、今まで生成した組み合わせを格納したリスト zs をそのまま返します。最後の節で、x を選ばない組み合わせを comb n xs ys zs で生成し、その返り値を x を選ぶ組み合わせを求める comb の第 4 引数に渡します。これで生成した組み合わせをリストに格納することができます。
実行例を示します。
ghci> combinations' 2 [1..5] [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]] ghci> combinations' 3 [1..5] [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
次の関数を定義してください。
リスト : 解答例 (perm.hs)
repeatPerm :: Int -> [a] -> [[a]]
repeatPerm 0 _ = [[]]
repeatPerm n xs = [x:ys | x <- xs, ys <- repeatPerm (n - 1) xs]
repeatComb :: Int -> [a] -> [[a]]
repeatComb 0 _ = [[]]
repeatComb _ [] = []
repeatComb n ys@(x:xs) = map (x:) (repeatComb (n-1) ys) ++ repeatComb n xs
select :: [a] -> [(a, [a])]
select [] = []
select [x] = [(x, [])]
select (x:xs) = (x, xs) : map (\(y, ys) -> (y, x:ys)) (select xs)
derangement :: Int -> [[Int]]
derangement m = perm_sub 1 [1 .. m]
where
perm_sub _ [] = [[]]
perm_sub n xs = [y:zs | (y, ys) <- select xs, y /= n, zs <- perm_sub (n + 1) ys]
ghci> :l perm.hs [1 of 1] Compiling Main ( perm.hs, interpreted ) Ok, one module loaded. ghci> repeatPerm 2 [1,2,3] [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]] ghci> repeatPerm 2 [1,2,3,4] [[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1], [4,2],[4,3],[4,4]] ghci> repeatPerm 3 [1,2,3] [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1], [2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2], [3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]] ghci> repeatComb 2 [1,2,3] [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]] ghci> repeatComb 2 [1,2,3,4] [[1,1],[1,2],[1,3],[1,4],[2,2],[2,3],[2,4],[3,3],[3,4],[4,4]] ghci> repeatComb 3 [1,2,3] [[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]] ghci> derangement 3 [[2,3,1],[3,1,2]] ghci> derangement 4 [[2,1,4,3],[2,3,4,1],[2,4,1,3],[3,1,4,2],[3,4,1,2],[3,4,2,1],[4,1,2,3],[4,3,1,2], [4,3,2,1]]