2

众所周知,列表的幂集: {1,2,3,4} is {{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3},{4},{1,4},{2,4},{1,2,4},{3,4},{1,3,4},{2,3,4},{1,2,3,4}}

我为这个问题得到的haskell代码是:

potencia [] = [[]]

potencia (a:bs) = potencia bs ++ map (a:) (potencia bs)

现在,我如何获得相同长度的子列表列表?例如,上面的列表将生成下一个长度为 3 = 的子列表列表{{1,2,3},{1,2,4},{1,3,4}}

我是学生对不起我的英语,提前谢谢... XD

4

2 回答 2

6

怎么样

sublists  _     0 = [[]]
sublists  []    _ = []
sublists (x:xs) n = sublists xs n ++ map (x:) (sublists xs $ n - 1)

这与您拥有的代码非常相似,但只有两个递减参数,即长度和列表。

此外,对于更高级的 Haskeller

powerset = flip runCont id . foldM step [[]]
  where step xs x = cont $ \c -> c xs ++ c (map (x:) xs)

是一个没有使用延续的递归的 powerset 实现。对函数做同样sublists的事情是一个有趣的挑战。

于 2013-09-03T01:45:08.773 回答
5

我只是在想

subsequencesOf :: Int -> [a] -> [[a]]
subsequencesOf n = filter ((== n) . length) . subsequences

哪个会给你

> subsequencesOf 3 [1, 2, 3, 4]
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

虽然我觉得这不是一个操作很奇怪,Data.Set而且这Set不是一个单子(因此有它自己的版本replicateM。)我想那里可能会有障碍。

于 2013-09-03T05:34:20.440 回答