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

问题描述

创建将Haskell中的一个（偶数）列表分为两个的所有可能性的最直接/最有效的方法是什么？我玩弄了所有列表的排列，但是这会增加许多额外功能 - 所有的情况下，每一半都包含相同的元素，只是按不同的顺序。例如，

  [1,2,3,4]应该产生类似于：
 
 [ 1,2,3,4] 
 [1,3,2,4] 
 [1,4,2,3] 
  

编辑：感谢您的评论 - 元素顺序和结果类型对于我来说比概念更重要 - 从一个表达所有两个组group，元素顺序不重要。

解决方案

这是一个紧跟定义的实现。

第一个元素总是进入左侧组。之后，我们将下一个head元素添加到一个或另一个组中。如果其中一个组变得太大，就没有选择了，我们必须把所有剩下的组合加入到较短的组中。

  divide :: [a]  - > [（[a]，[a]）] 
 divide [] = [（[]，[]）] 
 divide（x：xs）= go（[x]，[]，xs， 1，length xs）[] 
其中
 go（a，b，[]，i，j）zs =（a，b）：zs  -  i == lengh a  - 长度b 
 go（a，b，s @（x：xs），i，j）zs  -  j ==长度s 
 | i> = j =（a，b ++ s）：zs 
 | （-i）> = j =（a ++ s，b）：zs 
 | （x，a，b，xs，i + 1，j-1） > 
 
 
 
这产生 
 
 
  * Main>除[1,2,3,4] 
 [（[2,1]，[3,4]），（[3,1]，[2,4]），（[1,4]， [3,2]）] 
  
具有一个长度列表的限制是不必要的：
  * Main>除[1,2,3] 
 [（[2,1]，[3]），（[3,1]，[2]），（[1]，[3,2]）] 
  
 （为了提高效率，代码被重新写入差异列表 code> go2 A zs == go1 A ++ zs ）。 
 
 
 
  edit： 
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]
Edit: 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. 


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
This produces
*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])]
(the code was re-written in the "difference-list" style for efficiency: 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屋！