推广组合函数？

Question

我一直在Haskell上解决一些组合问题,所以我写下了这两个函数:

permutations :: (Eq a) => [a] -> [[a]]
permutations [] = [[]]
permutations list = do
    x  <- list
    xs <- permutations (filter (/= x) list)
    return (x : xs)

combinations :: (Eq a, Ord a) => Int -> [a] -> [[a]]
combinations 0 _ = [[]]
combinations n list = do
    x  <- list
    xs <- combinations (n-1) (filter (> x) list)
    return (x : xs)

其工作原理如下:

*Main> permutations [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
*Main> combinations 2 [1,2,3,4]
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

那些令人不舒服的相似,所以我不得不抽象它.我写了以下抽象:

combinatoric next [] = [[]]
combinatoric next list = do
    x  <- list
    xs <- combinatoric next (next x list)
    return (x : xs)

它接收一个控制如何过滤列表元素的函数.它可用于轻松定义排列:

permutations :: (Eq a) => [a] -> [[a]]
permutations = combinatoric (\ x ls -> filter (/= x) ls)

但我无法定义combinations这种方式,因为它带有一个state(n).我可以combinatoric通过一个额外的状态论证扩展它,但是它变得太笨重了,我记得在类似的情况下这种方法是不必要的.因此,我想知道:是否可以定义combinations使用combinatorics？如果没有,那么combinatorics成功包含两种功能的更好的抽象是什么？

Answer 1

这不是你问题的直接答案(对不起),但我不认为你的代码是正确的.这些Eq和Ord约束让我失望 - 它们不应该是必要的 - 所以我写了几个QuickCheck属性.

prop_numberOfPermutations xs = length (permutations xs) === factorial (length xs)
    where _ = (xs :: [Int])  -- force xs to be instantiated to [Int]

prop_numberOfCombinations (Positive n) (NonEmpty xs) = n <= length xs ==>
        length (combinations n xs) === choose (length xs) n
    where _ = (xs :: [Int])


factorial :: Int -> Int
factorial x = foldr (*) 1 [1..x]

choose :: Int -> Int -> Int
choose n 0 = 1
choose 0 r = 0
choose n r = choose (n-1) (r-1) * n `div` r

第一个属性检查该长度的列表的置换的数量n是n!.第二检查到的长度的列表的R-组合的数量n是C(n, r).当我针对您的定义运行它们时,这两个属性都会失败:

ghci> quickCheck prop_numberOfPermutations
*** Failed! Falsifiable (after 5 tests and 4 shrinks):    
[0,0,0]
3 /= 6
ghci> quickCheck prop_numberOfCombinations 
*** Failed! Falsifiable (after 4 tests and 1 shrink):     
Positive {getPositive = 2}
NonEmpty {getNonEmpty = [3,3]}
0 /= 1

当输入列表包含重复元素时,您的函数看起来会失败.为不正确的实现编写抽象不是一个好主意 - 在你走路之前不要尝试运行!您可能会发现阅读标准库定义的源代码很有帮助permutations,它没有Eq约束.