根据长度过滤子集？
Filter subsets based on length?
正在尝试使用过滤器提取长度为 k 的子集。不确定如何处理？该列表有 100 个元素。
subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = [zs | ys <- subsets xs, zs <- [ys, (x:ys)]]
如果我使用过滤器，这就是我认为的：
filter (length(3)) subsets [1,2,3,4,5]
但我可能错了。如果有不同的方法而不是过滤器？我是 haskell 的新手，所以不太确定。
当我在过滤过程中遇到一些困惑时，我会升级并使用 foldr 在这种情况下会很简单：
filterLength3 = foldr (\x rs -> if (length x) == 3 then x : rs else rs) []
filterLength3 (subsets [1,2,3,4,5])
output
=> [[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]]
Edit
想了很多，在chi的帮助下，请教终于解决了：
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]]
现在你可以把你的怪物变成一个小木偶了：
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
这是不使用过滤器的长度为 n 的子集的通用解决方案。
我们的初始列表是 x:xs，请注意，我们可以将这些子集划分为包含 x 的子集和不包含 x 的子集。这向我们展示了一个很好的递归结构；第一个分区是 x 前置到 xs 的每个长度 - (n-1) 个子集，第二个分区只是 xs.
的长度 -n 个子集
subsetsOfLength n (x:xs) = map (x:) (subsetsOfLength (n-1) xs) ++ subsetsOfLength n xs
我们只需要基本情况。有单个长度为0的子集，没有一个子集比原来的大：
subsets 0 _ = [[]]
subsets _ [] = []
将这些基础放在递归步骤之上并在其上添加适当的类型签名，我们就完成了。
λ> subsetsOfLength 3 [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]]
λ> length $ subsetsOfLength 5 [1..100]
252
不错。
小心。 (++) 很慢；如果您在编译时知道您将使用的长度， 可能会更高效。不过，对此并不完全确定。此外，根据值，您可能会很好地交换 (++) 的操作数。我还没有算过。
100个元素的列表的子集数量约为2100≃1.26*1030，这是一个非常庞大的数字。所以 filter 的方法似乎并不实用。这个问题应该通过处理只包含 1 到 100 之间的几个数字的列表来解决。
所以我们的目标是编写一个名为kSubsets的函数，其中returns基数k的所有子集的列表：
kSubsets :: Int -> [a] -> [[a]]
其中 k 是第一个参数。
基于递归列表处理的解决方案：
构建 kSubsets 功能的一种可能方法是使用辅助 kIndexSubsets 函数计算元素从零开始的索引，而不是元素本身。 kIndexSubsets 函数可以用递归的方式编写。
在那种情况下，kSubsets 函数本质上是一个包装器，它将元素索引映射到实际的列表元素。这给出了以下代码：
import qualified Data.Map as M
import qualified Data.Maybe as Mb
import qualified Data.List as L
kIndexSubsets :: Int -> Int -> [[Int]]
kIndexSubsets 0 _ = [[]]
kIndexSubsets k nn =
-- first element chosen must leave room for (k-1) elements after itself
let lastChoice = if (k > nn)
then error "k above nn in kIndexSubsets"
else (nn -k)
choices = [0 .. lastChoice]
-- for each possible first element, recursively compute
-- all the possible tails:
fn hd = let tails1 = kIndexSubsets (k-1) (nn - (hd+1))
-- rebase subsequent indexes:
tails2 = map (map (\x -> (x+hd+1))) tails1
in -- add new leftmost element:
map (\ls -> hd:ls) tails2
in
concatMap fn choices
-- return the list of all subsets of ls having k elements:
kSubsets :: Int -> [a] -> [[a]]
kSubsets 0 _ = [[]]
kSubsets k ls =
let nn = length ls
-- need a map for fast access to elements of ls:
ma = M.fromList $ zip [0..] ls
extractor ix = Mb.fromJust(M.lookup ix ma)
indexSubSets = kIndexSubsets k nn
in
map (map extractor) indexSubSets
我们现在可以测试我们的 kSubsets 功能。这涉及检查结果输出列表的长度是否符合经典组合公式，即 n!/(k! * (n-k)!) 其中 n 是输入列表的长度。
*Main> let ls = "ABCDEFGH"
*Main> kSubsets 0 ls
[""]
*Main> kSubsets 1 ls
["A","B","C","D","E","F","G","H"]
*Main> kSubsets 2 ls
["AB","AC","AD","AE","AF","AG","AH","BC","BD","BE","BF","BG","BH","CD","CE","CF","CG","CH","DE","DF","DG","DH","EF","EG","EH","FG","FH","GH"]
*Main> kSubsets 3 ls
["ABC","ABD","ABE","ABF","ABG","ABH","ACD","ACE","ACF","ACG","ACH","ADE","ADF","ADG","ADH","AEF","AEG","AEH","AFG","AFH","AGH","BCD","BCE","BCF","BCG","BCH","BDE","BDF","BDG","BDH","BEF","BEG","BEH","BFG","BFH","BGH","CDE","CDF","CDG","CDH","CEF","CEG","CEH","CFG","CFH","CGH","DEF","DEG","DEH","DFG","DFH","DGH","EFG","EFH","EGH","FGH"]
*Main>
*Main> kSubsets 7 ls
["ABCDEFG","ABCDEFH","ABCDEGH","ABCDFGH","ABCEFGH","ABDEFGH","ACDEFGH","BCDEFGH"]
*Main>
*Main> kSubsets 8 ls
["ABCDEFGH"]
*Main>
*Main>
*Main> div ((100*99*98)::Integer) ((2*3)::Integer)
161700
*Main>
*Main> length $ kSubsets 3 [ 1 .. 100 ]
161700
*Main>
*Main> div ((100*99*98*97*96)::Integer) ((2*3*4*5)::Integer)
75287520
*Main> length $ kSubsets 5 [ 1 .. 100 ]
75287520
*Main>
kSubsets 3 [ 1 .. 100 ] 的评估在普通 x86-64 Linux 机器上花费不到 50 毫秒。
基于状态机的替代解决方案：
所选索引的（反向）列表被视为自动机的状态，我们逐步推进状态，直到不再可能为止，此时子列表列表已完成。
基本上，如果最右边的索引有前进的空间，那很好，否则我们递归推进列表的其余部分，然后将最右边的索引尽可能向左移动。
该方法为 kIndexSubsets 提供了替代源代码，其中关键部分是 ksAdvance 步进函数：
import qualified Data.Map as M
import qualified Data.Maybe as Mb
import qualified Data.List as L
-- works on the *reversed* list of chosen indexes:
ksAdvance :: Int -> Int -> Maybe [Int] -> Maybe [Int]
ksAdvance k nn Nothing = Nothing
ksAdvance k nn (Just []) = Nothing
ksAdvance k nn (Just (h:rls)) =
if (h == (nn-1))
then -- cannot advance rightmost index, so must recurse
let mbols2 = ksAdvance (k-1) (nn-1) (Just rls)
in
case mbols2 of
Nothing -> Nothing
Just ols2 -> let y = ((head ols2)+1) in Just (y:ols2)
else -- just advance rightmost index:
Just ((h+1):rls)
kIndexSubsets :: Int -> Int -> [[Int]]
kIndexSubsets 0 _ = [[]]
kIndexSubsets k nn =
let startList = reverse $ [ 0 .. (k-1) ]
cutList = takeWhile Mb.isJust
mbls = cutList $ iterate (ksAdvance k nn) (Just startList)
in
map (reverse . Mb.fromJust) mbls
这个算法似乎比第一个算法占用更少的内存而且速度更快。
使用此主程序进行快速性能测试，100 个元素中有 5 个子集，生成 75287520 个子集：
kSubsets :: Int -> [a] -> [[a]]
kSubsets 0 _ = [[]]
kSubsets k ls =
let nn = length ls
-- need a map for fast access to elements of ls:
ma = M.fromList $ zip [0..] ls
eltFromIndex = \ix -> Mb.fromJust (M.lookup ix ma)
indexSubSets = kIndexSubsets k nn
in
map (map eltFromIndex) indexSubSets
main = do
let nn = 100
let k = 5
let ls = [ 1 .. nn ]::[Int]
let str = "count of " ++ (show k) ++ " out of " ++ (show nn) ++
" elements subsets = " ++ (show $ length (kSubsets k ls))
putStrLn $ str
内存性能提升：
$ /usr/bin/time ./kSubsets03.x +RTS -s
count of 5 out of 100 elements subsets = 75287520
4,529,861,272 bytes allocated in the heap
623,240 bytes copied during GC
44,504 bytes maximum residency (2 sample(s))
29,224 bytes maximum slop
2 MB total memory in use (0 MB lost due to fragmentation)
...
Productivity 98.4% of total user, 98.5% of total elapsed
0.70user 0.00system 0:00.72elapsed 99%CPU (0avgtext+0avgdata 4724maxresident)k
0inputs+0outputs (0major+436minor)pagefaults 0swaps
$
还没有 Fortran 好，但已经接近了:-)
正在尝试使用过滤器提取长度为 k 的子集。不确定如何处理？该列表有 100 个元素。
subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = [zs | ys <- subsets xs, zs <- [ys, (x:ys)]]
如果我使用过滤器，这就是我认为的：
filter (length(3)) subsets [1,2,3,4,5]
但我可能错了。如果有不同的方法而不是过滤器？我是 haskell 的新手，所以不太确定。
当我在过滤过程中遇到一些困惑时，我会升级并使用 foldr 在这种情况下会很简单：
filterLength3 = foldr (\x rs -> if (length x) == 3 then x : rs else rs) []
filterLength3 (subsets [1,2,3,4,5])
output
=> [[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]]
Edit
想了很多，在chi的帮助下，请教
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]]
现在你可以把你的怪物变成一个小木偶了：
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
这是不使用过滤器的长度为 n 的子集的通用解决方案。
我们的初始列表是 x:xs，请注意，我们可以将这些子集划分为包含 x 的子集和不包含 x 的子集。这向我们展示了一个很好的递归结构；第一个分区是 x 前置到 xs 的每个长度 - (n-1) 个子集，第二个分区只是 xs.
subsetsOfLength n (x:xs) = map (x:) (subsetsOfLength (n-1) xs) ++ subsetsOfLength n xs
我们只需要基本情况。有单个长度为0的子集，没有一个子集比原来的大：
subsets 0 _ = [[]]
subsets _ [] = []
将这些基础放在递归步骤之上并在其上添加适当的类型签名，我们就完成了。
λ> subsetsOfLength 3 [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]]
λ> length $ subsetsOfLength 5 [1..100]
252
不错。
小心。 (++) 很慢；如果您在编译时知道您将使用的长度，(++) 的操作数。我还没有算过。
100个元素的列表的子集数量约为2100≃1.26*1030，这是一个非常庞大的数字。所以 filter 的方法似乎并不实用。这个问题应该通过处理只包含 1 到 100 之间的几个数字的列表来解决。
所以我们的目标是编写一个名为kSubsets的函数，其中returns基数k的所有子集的列表：
kSubsets :: Int -> [a] -> [[a]]
其中 k 是第一个参数。
基于递归列表处理的解决方案：
构建 kSubsets 功能的一种可能方法是使用辅助 kIndexSubsets 函数计算元素从零开始的索引，而不是元素本身。 kIndexSubsets 函数可以用递归的方式编写。
在那种情况下，kSubsets 函数本质上是一个包装器，它将元素索引映射到实际的列表元素。这给出了以下代码：
import qualified Data.Map as M
import qualified Data.Maybe as Mb
import qualified Data.List as L
kIndexSubsets :: Int -> Int -> [[Int]]
kIndexSubsets 0 _ = [[]]
kIndexSubsets k nn =
-- first element chosen must leave room for (k-1) elements after itself
let lastChoice = if (k > nn)
then error "k above nn in kIndexSubsets"
else (nn -k)
choices = [0 .. lastChoice]
-- for each possible first element, recursively compute
-- all the possible tails:
fn hd = let tails1 = kIndexSubsets (k-1) (nn - (hd+1))
-- rebase subsequent indexes:
tails2 = map (map (\x -> (x+hd+1))) tails1
in -- add new leftmost element:
map (\ls -> hd:ls) tails2
in
concatMap fn choices
-- return the list of all subsets of ls having k elements:
kSubsets :: Int -> [a] -> [[a]]
kSubsets 0 _ = [[]]
kSubsets k ls =
let nn = length ls
-- need a map for fast access to elements of ls:
ma = M.fromList $ zip [0..] ls
extractor ix = Mb.fromJust(M.lookup ix ma)
indexSubSets = kIndexSubsets k nn
in
map (map extractor) indexSubSets
我们现在可以测试我们的 kSubsets 功能。这涉及检查结果输出列表的长度是否符合经典组合公式，即 n!/(k! * (n-k)!) 其中 n 是输入列表的长度。
*Main> let ls = "ABCDEFGH"
*Main> kSubsets 0 ls
[""]
*Main> kSubsets 1 ls
["A","B","C","D","E","F","G","H"]
*Main> kSubsets 2 ls
["AB","AC","AD","AE","AF","AG","AH","BC","BD","BE","BF","BG","BH","CD","CE","CF","CG","CH","DE","DF","DG","DH","EF","EG","EH","FG","FH","GH"]
*Main> kSubsets 3 ls
["ABC","ABD","ABE","ABF","ABG","ABH","ACD","ACE","ACF","ACG","ACH","ADE","ADF","ADG","ADH","AEF","AEG","AEH","AFG","AFH","AGH","BCD","BCE","BCF","BCG","BCH","BDE","BDF","BDG","BDH","BEF","BEG","BEH","BFG","BFH","BGH","CDE","CDF","CDG","CDH","CEF","CEG","CEH","CFG","CFH","CGH","DEF","DEG","DEH","DFG","DFH","DGH","EFG","EFH","EGH","FGH"]
*Main>
*Main> kSubsets 7 ls
["ABCDEFG","ABCDEFH","ABCDEGH","ABCDFGH","ABCEFGH","ABDEFGH","ACDEFGH","BCDEFGH"]
*Main>
*Main> kSubsets 8 ls
["ABCDEFGH"]
*Main>
*Main>
*Main> div ((100*99*98)::Integer) ((2*3)::Integer)
161700
*Main>
*Main> length $ kSubsets 3 [ 1 .. 100 ]
161700
*Main>
*Main> div ((100*99*98*97*96)::Integer) ((2*3*4*5)::Integer)
75287520
*Main> length $ kSubsets 5 [ 1 .. 100 ]
75287520
*Main>
kSubsets 3 [ 1 .. 100 ] 的评估在普通 x86-64 Linux 机器上花费不到 50 毫秒。
基于状态机的替代解决方案：
所选索引的（反向）列表被视为自动机的状态，我们逐步推进状态，直到不再可能为止，此时子列表列表已完成。
基本上，如果最右边的索引有前进的空间，那很好，否则我们递归推进列表的其余部分，然后将最右边的索引尽可能向左移动。
该方法为 kIndexSubsets 提供了替代源代码，其中关键部分是 ksAdvance 步进函数：
import qualified Data.Map as M
import qualified Data.Maybe as Mb
import qualified Data.List as L
-- works on the *reversed* list of chosen indexes:
ksAdvance :: Int -> Int -> Maybe [Int] -> Maybe [Int]
ksAdvance k nn Nothing = Nothing
ksAdvance k nn (Just []) = Nothing
ksAdvance k nn (Just (h:rls)) =
if (h == (nn-1))
then -- cannot advance rightmost index, so must recurse
let mbols2 = ksAdvance (k-1) (nn-1) (Just rls)
in
case mbols2 of
Nothing -> Nothing
Just ols2 -> let y = ((head ols2)+1) in Just (y:ols2)
else -- just advance rightmost index:
Just ((h+1):rls)
kIndexSubsets :: Int -> Int -> [[Int]]
kIndexSubsets 0 _ = [[]]
kIndexSubsets k nn =
let startList = reverse $ [ 0 .. (k-1) ]
cutList = takeWhile Mb.isJust
mbls = cutList $ iterate (ksAdvance k nn) (Just startList)
in
map (reverse . Mb.fromJust) mbls
这个算法似乎比第一个算法占用更少的内存而且速度更快。
使用此主程序进行快速性能测试，100 个元素中有 5 个子集，生成 75287520 个子集：
kSubsets :: Int -> [a] -> [[a]]
kSubsets 0 _ = [[]]
kSubsets k ls =
let nn = length ls
-- need a map for fast access to elements of ls:
ma = M.fromList $ zip [0..] ls
eltFromIndex = \ix -> Mb.fromJust (M.lookup ix ma)
indexSubSets = kIndexSubsets k nn
in
map (map eltFromIndex) indexSubSets
main = do
let nn = 100
let k = 5
let ls = [ 1 .. nn ]::[Int]
let str = "count of " ++ (show k) ++ " out of " ++ (show nn) ++
" elements subsets = " ++ (show $ length (kSubsets k ls))
putStrLn $ str
内存性能提升：
$ /usr/bin/time ./kSubsets03.x +RTS -s
count of 5 out of 100 elements subsets = 75287520
4,529,861,272 bytes allocated in the heap
623,240 bytes copied during GC
44,504 bytes maximum residency (2 sample(s))
29,224 bytes maximum slop
2 MB total memory in use (0 MB lost due to fragmentation)
...
Productivity 98.4% of total user, 98.5% of total elapsed
0.70user 0.00system 0:00.72elapsed 99%CPU (0avgtext+0avgdata 4724maxresident)k
0inputs+0outputs (0major+436minor)pagefaults 0swaps
$
还没有 Fortran 好，但已经接近了:-)