获取haskell中所有非减少列表集的列表

Question

如何生成具有当前长度的列表元素的所有可能的非减少集？

getSets :: [Int] -> Int -> [[Int]]
...

> getSets [0..9] 3
[[0,0,0],[0,0,1]..[3,9,9],[4,4,4]..[8,9,9],[9,9,9]]

Answer 1

getSets s n = filter nonDec $ replicateM n s
  where nonDec xs = and $ zipWith (>=) (drop 1 xs) xs

Answer 2

让我们开始有点简单,使用一个函数从给定的列表元素生成给定大小的所有集合:

getAllSets :: [Int] -> Int -> [[Int]]
getAllSets _  0 = [[]]
getAllSets xs n = [(x:ys) | x <- xs, ys <- getAllSets xs (n-1)]

您可以将此函数视为一次构建一个元素.它添加x到每个较短的集合的前面ys,并且它用于尽可能多的元素xs.

我们能做什么来得到最终答案是决定不为每个元素构建一个更长的集合xs,但仅限于那些x小于或等于每个元素的集合ys:

getSets :: [Int] -> Int -> [[Int]]
getSets _  0 = [[]]
getSets xs n = [(x:ys) | x <- xs, ys <- getSets xs (n-1), all (x <=) ys]

这是一个很好看的解决方案,但它比我们实际需要的工作更多.毕竟,为什么要x与每个元素进行比较ys？我们知道这ys已经是正确的顺序,因为我们以递归的方式构建它,所以让我们确保x小于或等于第一个元素ys,如果有的话:

getSets' :: [Int] -> Int -> [[Int]]
getSets' _  0 = [[]]
getSets' xs n = [(x:ys) | x <- xs, 
                          ys <- getSets' xs (n-1), 
                          null ys || x <= head ys]

更新:除了结合Thomas M. DuBuisson更清晰的谓词之外,我还对他的chrisdb和我的解决方案进行了基准测试:http://hpaste.org/50195

更新x2:修复了错误的Criterion标签; 基准测试是正确的,但输出结果令人困惑.