根据长度过滤子集? [英] Filter subsets based on length?

问题描述

尝试使用过滤器提取长度为k的子集.不确定如何处理?该列表包含 100个元素.

Trying to extract the subsets with length k using filter. Not sure how to approach it? The list has 100 elements.

subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = [zs | ys <- subsets xs, zs <- [ys, (x:ys)]]

如果我使用过滤器，这就是我的想法:

If i use filter this is what i thought it would be:

filter (length(3)) subsets [1,2,3,4,5]

但是我可能错了.是否有其他方法而不是过滤器?我是Haskell的新手，所以不确定.

But i'm probably wrong. If there is a different approach rather than filter? I'm new to haskell so not exactly sure.

推荐答案

当我在过滤方面遇到一些困惑时，我进行了升级，并使用foldr，在这种情况下将非常简单:

When I get stuck with a little confusion in filtering, I go a level up and use foldr in this case would be as simple as:

filterLength3 = foldr (\x rs -> if (length x) == 3 then  x : rs else rs) [] 

filterLength3 (subsets [1,2,3,4,5])

输出

=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,5],[1,3,5],[2,3,5],[1,4,5],[2,4,5],[3,4,5]]

带有filter的应该是:

filter ((==3) . length) (subsets [1,2,3,4,5])

=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,5],[1,3,5],[2,3,5],[1,4,5],[2,4,5],[3,4,5]]

编辑

经过深思熟虑，并在chi的帮助下，并提出了以下问题:问题我能够解决它:

After thinking a lot, and with the help of c and asking this question I was able to solve it:

import Data.List

subsetsOfThree ws = [ [x,y,z] | (x:xs) <- tails ws, (y:ys) <- tails xs, z <- ys ]

一些例子:

  subsetsOfThree [1..3]
=> [[1,2,3]]
   subsetsOfThree [1..4]
=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
   subsetsOfThree [1..5]
=> [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
   subsetsOfThree [1..10]
=> [[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],[1,2,9],[1,2,10],[1,3,4],[1,3,5],[1,3,6],[1,3,7],[1,3,8],[1,3,9],[1,3,10],[1,4,5],[1,4,6],[1,4,7],[1,4,8],[1,4,9],[1,4,10],[1,5,6],[1,5,7],[1,5,8],[1,5,9],[1,5,10],[1,6,7],[1,6,8],[1,6,9],[1,6,10],[1,7,8],[1,7,9],[1,7,10],[1,8,9],[1,8,10],[1,9,10],[2,3,4],[2,3,5],[2,3,6],[2,3,7],[2,3,8],[2,3,9],[2,3,10],[2,4,5],[2,4,6],[2,4,7],[2,4,8],[2,4,9],[2,4,10],[2,5,6],[2,5,7],[2,5,8],[2,5,9],[2,5,10],[2,6,7],[2,6,8],[2,6,9],[2,6,10],[2,7,8],[2,7,9],[2,7,10],[2,8,9],[2,8,10],[2,9,10],[3,4,5],[3,4,6],[3,4,7],[3,4,8],[3,4,9],[3,4,10],[3,5,6],[3,5,7],[3,5,8],[3,5,9],[3,5,10],[3,6,7],[3,6,8],[3,6,9],[3,6,10],[3,7,8],[3,7,9],[3,7,10],[3,8,9],[3,8,10],[3,9,10],[4,5,6],[4,5,7],[4,5,8],[4,5,9],[4,5,10],[4,6,7],[4,6,8],[4,6,9],[4,6,10],[4,7,8],[4,7,9],[4,7,10],[4,8,9],[4,8,10],[4,9,10],[5,6,7],[5,6,8],[5,6,9],[5,6,10],[5,7,8],[5,7,9],[5,7,10],[5,8,9],[5,8,10],[5,9,10],[6,7,8],[6,7,9],[6,7,10],[6,8,9],[6,8,10],[6,9,10],[7,8,9],[7,8,10],[7,9,10],[8,9,10]]

现在您可以使您的怪物变成一个小木偶:

And now you are able to make your monster a little puppet:

  length $ subsetsOfThree [1..10]
=> 120
   length $ subsetsOfThree [1..20]
=> 1140
   length $ subsetsOfThree [1..50]
=> 19600
   length $ subsetsOfThree [1..100]
=> 161700
length $ subsetsOfThree [1..500]
=> 20708500

这篇关于根据长度过滤子集?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！