Haskellで1つ（偶数）のリストを2つに分割するすべての可能性を作成するための最も直接的で効率的な方法は何ですか？私はリストのすべての順列を分割することをいじりましたが、それは多くの余分なものを追加します-各半分が同じ要素を異なる順序で含むすべてのインスタンス。例えば、
[1,2,3,4] should produce something like:
[ [1,2], [3,4] ]
[ [1,3], [2,4] ]
[ [1,4], [2,3] ]
編集：コメントありがとうございます-要素の順序と結果のタイプは、概念よりも私にとって重要ではありません-1つのグループからのすべての2つのグループの表現であり、要素の順序は重要ではありません。
空でないリスト（長さが偶数n）のすべてのパーティションを2つの同じサイズの部分に見つけるために、繰り返しを避けるために、最初の要素が最初の部分にあると仮定できます。n/2 - 1次に、リストの末尾を長さの一部と長さの1つに分割するすべての方法を見つける必要がありますn/2。
-- not to be exported
splitLen :: Int -> Int -> [a] -> [([a],[a])]
splitLen 0 _ xs = [([],xs)]
splitLen _ _ [] = error "Oops"
splitLen k l ys@(x:xs)
| k == l = [(ys,[])]
| otherwise = [(x:us,vs) | (us,vs) <- splitLen (k-1) (l-1) xs]
++ [(us,x:vs) | (us,vs) <- splitLen k (l-1) xs]
適切に呼び出された場合、その分割を行います。それで
partitions :: [a] -> [([a],[a])]
partitions [] = [([],[])]
partitions (x:xs)
| even len = error "Original list with odd length"
| otherwise = [(x:us,vs) | (us,vs) <- splitLen half len xs]
where
len = length xs
half = len `quot` 2
重複を冗長に計算せずにすべてのパーティションを生成します。
ルキは良い点を上げます。繰り返される要素でリストを分割したいという可能性を考慮していません。それらを使用すると、少し複雑になりますが、それほど多くはありません。まず、リストを等しい要素にグループ化します（ここでは、Ord制約のためにのみEq実行されますが、それでも実行できますO(length²)）。考え方は似ています。繰り返しを避けるために、前半には2番目のグループよりも最初のグループの要素が多く含まれていると仮定します（または、最初のグループに偶数がある場合は、同じ数の同様の制限が次のグループにも当てはまりますグループなど）。
repartitions :: Ord a => [a] -> [([a],[a])]
repartitions = map flatten2 . halves . prepare
where
flatten2 (u,v) = (flatten u, flatten v)
prepare :: Ord a => [a] -> [(a,Int)]
prepare = map (\xs -> (head xs, length xs)) . group . sort
halves :: [(a,Int)] -> [([(a,Int)],[(a,Int)])]
halves [] = [([],[])]
halves ((a,k):more)
| odd total = error "Odd number of elements"
| even k = [((a,low):us,(a,low):vs) | (us,vs) <- halves more] ++ [normalise ((a,c):us,(a,k-c):vs) | c <- [low + 1 .. min half k], (us,vs) <- choose (half-c) remaining more]
| otherwise = [normalise ((a,c):us,(a,k-c):vs) | c <- [low + 1 .. min half k], (us,vs) <- choose (half-c) remaining more]
where
remaining = sum $ map snd more
total = k + remaining
half = total `quot` 2
low = k `quot` 2
normalise (u,v) = (nz u, nz v)
nz = filter ((/= 0) . snd)
choose :: Int -> Int -> [(a,Int)] -> [([(a,Int)],[(a,Int)])]
choose 0 _ xs = [([],xs)]
choose _ _ [] = error "Oops"
choose need have ((a,k):more) = [((a,c):us,(a,k-c):vs) | c <- [least .. most], (us,vs) <- choose (need-c) (have-k) more]
where
least = max 0 (need + k - have)
most = min need k
flatten :: [(a,Int)] -> [a]
flatten xs = xs >>= uncurry (flip replicate)
これが、定義に厳密に従った実装です。
最初の要素は常に左側のグループに入ります。その後、次のヘッド要素を一方または他方のグループに追加します。グループの1つが大きくなりすぎると、選択の余地がなくなり、残りのすべてを短いグループに追加する必要があります。
divide :: [a] -> [([a], [a])]
divide [] = [([],[])]
divide (x:xs) = go ([x],[], xs, 1,length xs) []
where
go (a,b, [], i,j) zs = (a,b) : zs -- i == lengh a - length b
go (a,b, s@(x:xs), i,j) zs -- j == length s
| i >= j = (a,b++s) : zs
| (-i) >= j = (a++s,b) : zs
| otherwise = go (x:a, b, xs, i+1, j-1) $ go (a, x:b, xs, i-1, j-1) zs
これにより、
*Main> divide [1,2,3,4]
[([2,1],[3,4]),([3,1],[2,4]),([1,4],[3,2])]
偶数の長さのリストを持つという制限は不要です。
*Main> divide [1,2,3]
[([2,1],[3]),([3,1],[2]),([1],[3,2])]
（コードは効率のために「difference-list」スタイルで書き直されました:) go2 A zs == go1 A ++ zs。
編集：これはどのように機能しますか？石の山に座って、それを2つに分割することを想像してみてください。あなたは最初の石を横に置きますが、それは問題ではありません（つまり、左に言います）。次に、次の各石を配置する場所を選択します。2つの山のいずれかが比較して小さくなりすぎない限り、残りのすべての石を一度に配置する必要があります。
ダニエル・フィッシャーの答えは、問題を解決するための良い方法です。私はより悪い（より非効率的な）方法を提供しますが、より明らかに（私にとって）問題の説明に対応する方法を提供します。リストのすべてのパーティションを2つの等しい長さのサブリストに生成し、同等の定義に従って同等のサブリストを除外します。私が通常問題を解決する方法は、次のように開始することです。可能な限り明白なソリューションを作成し、それを徐々により効率的なソリューションに変換します（必要な場合）。
import Data.List (sort, nubBy, permutations)
type Partition a = ([a],[a])
-- Your notion of equivalence (sort to ignore the order)
equiv :: (Ord a) => Partition a -> Partition a -> Bool
equiv p q = canon p == canon q
where
canon (xs,ys) = sort [sort xs, sort ys]
-- All ordered partitions
partitions :: [a] -> [Partition a]
partitions xs = map (splitAt l) (permutations xs)
where
l = length xs `div` 2
-- All partitions filtered out by the equivalence
equivPartitions :: (Ord a) => [a] -> [Partition a]
equivPartitions = nubBy equiv . partitions
テスト
>>> equivPartitions [1,2,3,4]
[([1,2],[3,4]),([3,2],[1,4]),([3,1],[2,4])]
QuickCheckを使用してこの実装とDanielの実装との同等性をテストした後、重要な違いを見つけました。明らかに、私のものには(Ord a)制約が必要ですが、彼には必要ありません。これは、違いがどうなるかを示唆しています。特に、彼を与えると[0,0,0,0]、のコピーが3つあるリストが得られますが([0,0],[0,0])、私のものは1つのコピーしか与えられません。これらのどれが正しいかは指定されていません。ダニエルは、2つの出力リストを順序付けられたシーケンス（通常、そのタイプと見なされるもの）と見なす場合は自然であり、私のものは、それらをセットまたはバッグと見なす場合（この質問がそれらをどのように扱っているように見えるか）は自然です。
リスト内の値ではなく位置Ordを操作することにより、必要な実装から必要でない実装に移行することができます。私はこの変革を思いつきました。これは、ベンジャミン・ピアスが双方向プログラミングの研究に端を発していると私が信じているアイデアです。
import Data.Traversable
import Control.Monad.Trans.State
data Labelled a = Labelled { label :: Integer, value :: a }
instance Eq (Labelled a) where
a == b = compare a b == EQ
instance Ord (Labelled a) where
compare a b = compare (label a) (label b)
labels :: (Traversable t) => t a -> t (Labelled a)
labels t = evalState (traverse trav t) 0
where
trav x = state (\i -> i `seq` (Labelled i x, i + 1))
onIndices :: (Traversable t, Functor u)
=> (forall a. Ord a => t a -> u a)
-> forall b. t b -> u b
onIndices f = fmap value . f . labels
onIndicesonを使用してequivPartitionsもまったく高速化されませんがequiv、制約なしで、Danielと同じセマンティクス（結果まで）を使用でき、より素朴で明白な表現方法を使用できます。制約を取り除くための興味深い方法だと思いました。
ウィルの答えに触発されて、ずっと後に追加された私自身の一般化されたバージョン：
import Data.Map (adjust, fromList, toList)
import Data.List (groupBy, sort)
divide xs n evenly = divide' xs (zip [0..] (replicate n [])) where
evenPSize = div (length xs) n
divide' [] result = [result]
divide' (x:xs) result = do
index <- indexes
divide' xs (toList $ adjust (x :) index (fromList result)) where
notEmptyBins = filter (not . null . snd) $ result
partlyFullBins | evenly == "evenly" = map fst . filter ((<evenPSize) . length . snd) $ notEmptyBins
| otherwise = map fst notEmptyBins
indexes = partlyFullBins
++ if any (null . snd) result
then map fst . take 1 . filter (null . snd) $ result
else if null partlyFullBins
then map fst. head . groupBy (\a b -> length (snd a) == length (snd b)) . sort $ result
else []