Haskell生成预过滤的排列 [英] Haskell generating pre-filtered permutations

问题描述

有没有一种方法可以生成预先过滤的排列，而不是:

Is there a way to generated prefiltered permutations, that is rather than doing :

filter condition $ permutations list

排列功能可能会短路.例如:

The permutation function can short-circuited. For example :

perms [] = [[]]
perms xs = [ i:j | i <- xs, j <- perms $ delete i xs]

我尝试了一些明显的事情，例如:

I tried a few obvious things like :

perms xs = [ i:j | i <- xs, j <- filter condition $ perms $ delete i xs]

我认为将要发生的事情是，这会引出一条链，该链最终会在[]处出现，然后再进行备份，但是会一直过滤.但是，当输入大量文件时，可以加快处理速度.似乎没有发生这种情况，因为尝试对20个项目列表进行置换时会出现(ghci)停滞的情况，而该列表实际上只有很少的经过过滤的置换.

I thought what would happen is this would set off a chain which would end up at [] and then work back up, but filtering along the way. However when feeding it a long list and thus speeding up the process. This doesn't seem to happen as it bogged out (ghci) when trying to do a permutation of a 20 item list that would have only very few actually filtered permutations.

推荐答案

以do表示法进行递归编码非常简单.

Coding it up in do notation with recursion is pretty straightforward.

foo :: ([a] -> Bool) -> [a] -> [[a]]
foo p xs = bar ([],xs)
   where
   bar (acc,[]) = return acc
   bar (acc,xs) = do
                   (x,ys) <- picks xs      -- shrink the domain (ys)
                   if ( p (x:acc) )        -- test soon
                     then bar (x:acc,ys)   -- loop
                     else mzero            -- fail early

picks [] = []
picks (x : xs) = (x, xs) : [(y, x : ys) | (y, ys) <- picks xs]

picks来自此答案.

测试:

> foo (const True) [1..3]
[[3,2,1],[2,3,1],[3,1,2],[1,3,2],[2,1,3],[1,2,3]]

> foo (\(x:xs) -> not(null xs) || x > 1) [1..3]
[[3,1,2],[1,3,2],[2,1,3],[1,2,3]]

最后一个开始立即为[1..20]，[1..300]等产生其输出.

The last one starts producing its output immediately also for [1..20], [1..300] etc.

我敢肯定，这可以用更高层次的东西很好地表达出来.

I'm sure this can be expressed neatly with higher-level stuff.

这篇关于Haskell生成预过滤的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！