0

我正在用haskell编写一个combs函数它需要做的是,当我为它提供一副牌时,给我从那个大小为x的牌组中可能的每一种手组合

这是相关代码

combs :: Int -> [a] -> [[a]]
combs 0 _      = [[ ]]
combs i (x:xs) =  (filter (isLength i) y)
            where y = subs (x:xs)
combs _ _      = [ ]

isLength :: Int -> [a] -> Bool
isLength i x
        | length x == i = True
        | otherwise     = False

subs :: [a] -> [[a]]
subs [ ] = [[ ]]
subs (x : xs) = map (x:) ys ++ ys
            where ys = subs xs

但是,当我要求它计算梳子 5 [1..52] 时,例如一副牌中的 5 手牌,它不会提供结果,并且会持续运行很长时间
有谁知道问题出在哪里是以及如何加速这个算法?

4

2 回答 2

3

现在很难看出你想要做什么——但我想你遇到的问题是你会过滤和映射很多。

我认为获得所需内容的简单方法是:

module Combinations where

import Data.List (delete)

combs :: Eq a => Int -> [a] -> [[a]]
combs 0 _ = [[]]
combs i xs = [ y:ys | y <- xs, ys <- combs (i-1) (delete y xs) ]

使用deleteData.List

它应该足够懒惰才能快速找到您的组合 - 当然所有这些都需要一段时间;)

λ> take 5 $ combs 5 [1..52]
[[1,2,3,4,5],[1,2,3,4,6],[1,2,3,4,7],[1,2,3,4,8],[1,2,3,4,9]]

它是如何工作的

它是一种递归组合算法,通过y从所有卡片中选择第一张卡片来工作xs,然后递归获取s the rest of the handysfrom the deck without the selected card删除列表单子内的 xs and then putting it back togethery:ys`(此处使用列表理解)。

顺便说一句:有 311,875,200 个这样的套牌;)

没有列表理解的版本

这是一个没有理解的版本,以防您的系统在这里出现问题:

combs :: Eq a => Int -> [a] -> [[a]]
combs 0 _ = [[]]
combs i xs = do
  y <- xs
  ys <- combs (i-1) (delete y xs)
  return $ y:ys

将删除排列的版本

这用于Ord按升序对项目进行排序,并在此过程中删除与排列相关的重复项 - 预计此工作xs被预先排序!

请注意,chi 的版本使用较少的约束,并且可能也更加前瞻 - 但我认为这很好且易读,并且与之前的版本相得益彰,所以您可能会感兴趣。

我知道这不是在 Haskell/FP 中经常做的事情,你为最一般和最抽象的情况而奋斗,但我形成了一个最努力争取可读性和理解力的环境(为程序员编码,不仅为编译器) - 所以要温柔;)

combs' :: Ord a => Int -> [a] -> [[a]]
combs' 0 _  = [[]]
combs' i xs = [ y:ys | y <- xs, ys <- combs' (i-1) (filter (> y) xs) ]
于 2014-10-12T17:44:18.513 回答
3

要从您那里提取i项目,x:xs可以通过两种方式进行:

  • 您保留x, 并仅从中提取i-1元素xs
  • 你丢弃x,并从中提取所有i元素xs

因此,一个解决方案是:

comb :: Int -> [a] -> [[a]]
comb 0 _      = [[]]  -- only the empty list has 0 elements
comb _ []     = []    -- can not extract > 0 elements from []
comb i (x:xs) = [ x:ys | ys <- comb (i-1) xs ]  -- keep x case
                ++ comb i xs                    -- discard x case

顺便说一句,上面的代码还“证明”了一个著名的二项式系数递归公式。如果您参加过微积分课,您可能已经遇到过这个公式。让B(k,n) = length (comb k [1..n]),我们有

B(k+1,n+1) == B(k,n) + B(k+1,n)

这只是上面代码最后一行的直接结果。

于 2014-10-12T17:50:46.763 回答