4

リストの可能なすべてのサブリストのリストを含むリストを生成する関数を作成する必要があります。したがって、タイプは次のようにする必要があります。

partitions :: [a] -> [[[a]]]

そしてそれは与えるべきです：

パーティション [1..4] = [[[1],[2],[3],[4]], [[1,2],[3],[4]], [[1],[2 ,3],[4]], [[1,2,3],[4]], [[1],[2],[3,4]], [[1,2],[3,4] ]]、[[1]、[2,3,4]]、[[1,2,3,4]]]

リスト内包表記が最善の方法だと思います。これまでのところ、私は持っています:

partitions :: [a]  -> [[[a]]]
partitions (x:xs) = foldr insert [[]] (x:xs)
   where insert ys zs = ys:x:zs

これにより、予想どおり型エラーがスローされますが、修正方法がわかりません。明らかな何かが欠けていると感じています。助けていただければ幸いです。

4

1 に答える 1

9

直接再帰から始めます。分解して、長いリストの最初の要素にはどのような可能性があるでしょうか?

  1. これは、パーティション リストの 1 つの唯一の要素である場合があります。
  2. 複数の要素を持つパーティション リストの一部にすることができます。

あなたの例から、元の要素を順番に保持したいようです。そのため、各パーティションのメンバーは連続したサブリストにしかならないため、多少簡単になります。

だから私たちは始めることができます

partitions :: [a] -> [[[a]]]
partitions [] = [[]]    -- only one partition of an empty list, an empty partition
partitions (x:xs) = [[x]:part | part <- partitions xs] ++ [(x:ys):yss | (ys:yss) <- partitions xs]

利回り

*Partitions> partitions [1,2,3,4]
[[[1],[2],[3],[4]],[[1],[2],[3,4]],[[1],[2,3],[4]],[[1],[2,3,4]],[[1,2],[3],[4]],[[1,2],[3,4]],[[1,2,3],[4]],[[1,2,3,4]]]

希望の順番ではありません。それが重要な場合は、書き直さなければなりません。望ましい順序は、最初の要素の両方の選択肢を直接連続してリストするため、次のように書くことができます

partitions (x:xs) = partitions xs >>= \zs -> case zs of
                                               [] -> [[[x]]]
                                               (ys:yss) -> [[x]:ys:yss, (x:ys):yss]

空のパーティション (再帰の終わり) と空でないパーティションのケースを明示的に区別する必要があります。これは、上記では pattern にバインドすることによって暗黙的に行われました(ys:yss)。それは望ましい順序をもたらします

*Partitions> partitions [1,2,3,4]
[[[1],[2],[3],[4]],[[1,2],[3],[4]],[[1],[2,3],[4]],[[1,2,3],[4]],[[1],[2],[3,4]],[[1,2],[3,4]],[[1],[2,3,4]],[[1,2,3,4]]]

(>>=)リストモナドのバインドが であるという事実を利用してflip concatMap、バージョン

partitions (x:xs) = concatMap insert (partitions xs)
  where
    insert [] = [[[x]]]
    insert (ys:yss) = [[x]:ys:yss, (x:ys):yss]

より読みやすいかもしれません。

于 2012-11-18T21:49:19.977 に答える