在 Haskell 中将列表一分为二的所有可能性 [英] all possibilities of dividing a list in two in Haskell

问题描述

在 Haskell 中创建将一个(偶数)列表一分为二的所有可能性的最直接/最有效的方法是什么?我想拆分列表的所有排列，但这会增加许多额外的东西——每一半都包含相同元素的所有实例，只是顺序不同.例如，

What's the most direct/efficient way to create all possibilities of dividing one (even) list into two in Haskell? I toyed with splitting all permutations of the list but that would add many extras - all the instances where each half contains the same elements, just in a different order. For example,

[1,2,3,4] should produce something like:

[ [1,2],  [3,4] ]
[ [1,3],  [2,4] ]
[ [1,4],  [2,3] ]

感谢您的评论——元素的顺序和结果的类型对我来说不如概念重要——一组中所有两个组的表达，其中元素顺序不重要.

thank you for your comments -- the order of elements and the type of the result is less important to me than the concept - an expression of all two-groups from one group, where element order is unimportant.

推荐答案

这是一个实现，紧跟定义.

Here's an implementation, closely following the definition.

第一个元素总是进入左组.之后，我们将下一个 head 元素添加到一个或另一个组中.如果其中一组变得太大，则别无选择，我们必须将所有其余组添加到较短的组中.

The first element always goes into the left group. After that, we add the next head element into one, or the other group. If one of the groups becomes too big, there is no choice anymore and we must add all the rest into the the shorter group.

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])]

具有偶数长度列表的限制是不必要的:

The limitation of having an even length list is unnecessary:

*Main> divide [1,2,3]
[([2,1],[3]),([3,1],[2]),([1],[3,2])]

_{(为了提高效率，代码以差异列表"风格重写:go2 A zs == go1 A ++ zs).}

这是如何工作的?想象自己坐在一堆石头前，把它分成两半.你把第一块石头放在一边，哪一块并不重要(所以，左边，说).然后可以选择放置下一块石头的位置—除非相比之下两堆中的一堆变得太小，因此我们必须立即将所有剩余的石头放在那里.

edit: How does this work? Imagine yourself sitting at a pile of stones, dividing it into two. You put the first stone to a side, which one it doesn't matter (so, left, say). Then there's a choice where to put each next stone — unless one of the two piles becomes too small by comparison, and we thus must put all the remaining stones there at once.

这篇关于在 Haskell 中将列表一分为二的所有可能性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！