推广组合函数？

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，因为它带有一个状态 (n)。我可以用一个额外的状态参数来扩展 combinatoric，但那会变得太笨重，我记得这种方法是不必要的。因此，我想知道：是否可以使用 combinatorics 来定义 combinations？如果不是，那么 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

第一个属性检查 the number of permutations of a list of length n is n!. The second checks that the number of r-combinations of a list of length n is 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

当输入列表包含重复元素时，您的函数似乎失败了。为不正确的实现编写抽象不是一个好主意 - 在你可以走路之前不要尝试运行！您可能会发现阅读 the source code for the standard library's definition of permutations 很有帮助，它没有 Eq 约束。

Answer 2

首先让我们改进原有的功能。您假设所有元素在 permutations 的相等性方面都是不同的，并且它们是不同的并且具有 combinations 的排序。这些约束不是必需的，并且如其他答案中所述，代码可能会产生错误的结果。在 robustness principle 之后，让我们只接受不受约束的列表。为此，我们需要一个辅助函数来生成列表的所有可能拆分：

split :: [a] -> [([a], a, [a])]
split = loop []
  where
    loop _  []      = []
    loop rs (x:xs)  = (rs, x, xs) : loop (x:rs) xs

请注意，该实现会导致此函数返回的前缀被反转，但这不是我们所需要的。

这让我们可以编写泛型 permutations 和 combinations。

permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations list = do
    (pre, x, post) <- split list
    -- reversing 'pre' isn't really necessary, but makes the output
    -- order natural
    xs <- permutations (reverse pre ++ post)
    return (x : xs)

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

现在他们的共同点是：

在每一步他们选择一个元素输出，
更新要选择的元素列表并
满足某些条件后停止。

最后一点有点问题，至于permutations我们在可供选择的列表为空时结束，而对于combinations我们有一个计数器。这大概就是难以一概而论的原因。我们可以通过意识到 permutations 的步数等于输入列表的长度来解决这个问题，因此我们可以用重复次数来表达条件。

对于此类问题，使用 StateT s [] monad 来表达它们通常非常方便，其中 s 是我们正在处理的状态。在我们的例子中，它将是可供选择的元素列表。我们的组合函数的核心可以用 StateT [a] [] a 表示：从状态中选择一个元素并更新下一步的状态。由于有状态计算全部发生在 [] monad 中，我们自动分支所有可能性。有了它，我们可以定义一个通用函数：

import Control.Monad.State

combinatoric :: Int -> StateT [a] [] b -> [a] -> [[b]]
combinatoric n k = evalStateT $ replicateM n k

然后定义permutations和combinations通过指定适当的重复次数和核心StateT [a] [] a功能是什么：

permutations' :: [a] -> [[a]]
permutations' xs = combinatoric (length xs) f xs
  where
    f = StateT $ map (\(pre, x, post) -> (x, reverse pre ++ post)) . split


combinations' :: Int -> [a] -> [[a]]
combinations' n xs = combinatoric n f xs
  where
    f = StateT $ map (\(_, x, post) -> (x, post)) . split

推广组合函数？

Generalizing a combinatoric function?

algorithm

haskell

functional-programming