algorithm - 在 Haskell 中满足条件的所有大小为 N 的子集

Question

我想写一个函数，它接受一个列表并返回满足给定条件的所有可能子集的列表。 例如，我想要 [1,2,3,4] 的所有 3 尺寸子集，但没有包含 2 和 3 的任何子集。

$> func [1,2,3,4] 3
[[1,2,4],[1,3,4]]

为了生成所有大小为 N 的子集，我有以下函数(找到 here ):

kCombinations :: [a] -> Integer -> [[a]]
kCombinations _      0 = [[]]
kCombinations []     _ =  []
kCombinations (x:xs) k = withHead ++ withoutHead
  where withHead    = map (x:) (kCombinations xs (k-1))
        withoutHead = kCombinations xs k

我知道解决我的问题的最简单方法是首先生成所有组合，然后再使用过滤函数。但是对于像 kCombinations [1..30] 6 这样更大的问题，它需要很长时间才能完成。

你能告诉我如何在所有组合的生成过程中过滤掉一些数据吗？

Answer 1

可以改进 subsequencesOfSize user5402 提到的功能。比较 this和 this .这是因为 (l-n)在第二个版本中，所以 subsequencesOfSize 3 [1..350]等于subsequencesBySize [1..350] !! 347 , 因此创建了很多未使用的列表。

当通过谓词过滤子序列时 p它具有 p xs 的属性是真的意味着 all p (inits xs)是的，可以将谓词集成到子序列的生成中以获得更高的效率。谓词“不包含 2 和 3”就是这种情况。

这就是你想要的:

zapWith f    xs     []  = xs
zapWith f (x:xs) (y:ys) = f x y : zapWith f xs ys

filterCombs :: ([a] -> Bool) -> Int -> [a] -> [[a]]
filterCombs p n xs | n > length xs = [] 
filterCombs p n xs = go xs id !! n where
    go    []  ds = [[[]]]
    go (x:xs) ds
        | p (ds' []) = zapWith (++) ([] : map (map (x:)) with) without
        | otherwise  = without
        where
            ds'     = ds . (x:)
            with    = go xs ds'
            without = go xs ds

zapWith是有意不详尽的。 ds在go函数是一个差异列表，其中包含所有先前的元素。你可以阅读go像这样:如果属性 p适用于 <all previous elements of xs> ++ [x]然后包含与 x 的组合没有 x , 否则只包括没有 x .

一些例子:

conseq (x:y:xs) = succ x == y && conseq (y:xs)
conseq      xs  = True

main = do
    print $ filterCombs (\xs -> any (`notElem` xs) [2,3]) 3 [1..5]
    print $ filterCombs conseq 4 $ [1..8] ++ [8,7..1]
    print $ filterCombs (all (<= 10)) 9 [1..5000]

打印

[[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,4,5],[3,4,5]]
[[1,2,3,4],[1,2,3,4],[2,3,4,5],[2,3,4,5],[3,4,5,6],[3,4,5,6],[4,5,6,7],[4,5,6,7],[5,6,7,8],[5,6,7,8]]
[[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,8,10],[1,2,3,4,5,6,7,9,10],[1,2,3,4,5,6,8,9,10],[1,2,3,4,5,7,8,9,10],[1,2,3,4,6,7,8,9,10],[1,2,3,5,6,7,8,9,10],[1,2,4,5,6,7,8,9,10],[1,3,4,5,6,7,8,9,10],[2,3,4,5,6,7,8,9,10]]