生成具有给定长度的组合的更快方法，保留顺序 [英] A faster way of generating combinations with a given length, preserving the order

问题描述

TL;DR:我想要 filter ((== 4) . length) 的确切行为.子序列.仅使用 subsequences 也会创建可变长度的列表，这需要大量时间来处理.由于最终只需要长度为 4 的列表，我认为必须有更快的方法.

TL;DR: I want the exact behavior as filter ((== 4) . length) . subsequences. Just using subsequences also creates variable length of lists, which takes a lot of time to process. Since in the end only lists of length 4 are needed, I was thinking there must be a faster way.

我有一个函数列表.该列表的类型为 [Wor ->工作]

I have a list of functions. The list has the type [Wor -> Wor]

列表看起来像这样

[f1, f2, f3 .. fn]

我想要的是一个 n 函数列表的列表，同时保留这样的顺序

What I want is a list of lists of n functions while preserving order like this

输入:[f1, f2, f3 .. fn]

参数:4 个函数

输出:4 个函数的列表.

output : A list of lists of 4 functions.

如果子列表中有 f1，则预期输出将始终位于列表的 head.

Expected output would be where if there's an f1 in the sublist, it'll always be at the head of the list.

如果子列表中有 f2 并且子列表没有 f1，则 f2 将位于 head.如果 fn 在子列表中，它将位于 last.

If there's a f2 in the sublist and if the sublist doens't have f1, f2 would be at head. If fn is in the sublist, it'll be at last.

一般来说，如果列表中有一个 fx ，它永远不会在 f(x - 1) 的前面.

In general if there's a fx in the list, it never will be infront of f(x - 1) .

生成子列表时基本保持主列表的顺序.

Basically preserving the main list's order when generating sublists.

可以假设列表的长度总是大于给定的参数.

It can be assumed that length of list will always be greater then given argument.

我刚刚开始学习 Haskell，所以我还没有尝试那么多，但到目前为止，我已经尝试过:

I'm just starting to learn Haskell so I haven't tried all that much but so far this is what I have tried is this:

具有 subsequences 函数并对其应用 (filter (== 4) .length) 的生成排列似乎生成正确的排列 - 但它不保留顺序 -(它保留了顺序，我把它和我自己的功能混淆了).

Generation permutations with subsequences function and applying (filter (== 4) . length) on it seems to generate correct permutations -but it doesn't preserve order- (It preserves order, I was confusing it with my own function).

那我该怎么办?

另外，如果可能的话，Hackage 或 Stackage 中是否存在可以执行此操作的函数或函数组合?因为我想了解一下来源.

Also if possible, is there a function or a combination of functions present in Hackage or Stackage which can do this? Because I would like to understand the source.

推荐答案

你描述了一个不确定的take:

You describe a nondeterministic take:

ndtake :: Int -> [a] -> [[a]]
ndtake 0 _      = [[]]
ndtake n []     = []
ndtake n (x:xs) = map (x:) (ndtake (n-1) xs) ++ ndtake n xs

要么我们取一个x，然后再从xs 中取n-1 个；或者我们不采用 x 而是从 xs 获取更多的 n 元素.

Either we take an x, and have n-1 more to take from xs; or we don't take the x and have n more elements to take from xs.

运行:

> ndtake 3 [1..4]
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

<小时>

更新:您想要效率.如果我们确定输入列表是有限的，我们可以尽快停止:

---

Update: you wanted efficiency. If we're sure the input list is finite, we can aim at stopping as soon as possible:

ndetake n xs = go (length xs) n xs
    where
    go spare n _  | n >  spare = []
    go spare n xs | n == spare = [xs]
    go spare 0 _      =  [[]]
    go spare n []     =  []
    go spare n (x:xs) =  map (x:) (go (spare-1) (n-1) xs) 
                            ++     go (spare-1)  n   xs

尝试:

> length $ ndetake 443 [1..444]
444

前一个版本好像卡在这个输入上，但是后一个立即返回.

The former version seems to be stuck on this input, but the latter one returns immediately.

但是，正如 @dfeuer 在评论.我们可以实现同样的效率提升，同时保留更多的懒惰:

But, it measures the length of the whole list, and needlessly so, as pointed out by @dfeuer in the comments. We can achieve the same improvement in efficiency while retaining a bit more laziness:

ndzetake :: Int -> [a] -> [[a]]
ndzetake n xs | n > 0 = 
    go n (length (take n xs) == n) (drop n xs) xs
    where
    go n b p ~(x:xs)
         | n == 0 = [[]]
         | not b  = []
         | null p = [(x:xs)]
         | otherwise = map (x:) (go (n-1) b p xs)
                          ++ go n b (tail p) xs

现在最后一个测试也可以立即使用此代码.

Now the last test also works instantly with this code as well.

这里仍有改进的空间.与库函数subsequences 一样，搜索空间可以更加懒惰地探索.现在我们有

There's still room for improvement here. Just as with the library function subsequences, the search space could be explored even more lazily. Right now we have

> take 9 $ ndzetake 3 [1..]
[[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,2,11]]

但它可能会在将 5 强制退出输入列表之前找到 [2,3,4].我们可以把它留作练习吗?

but it could be finding [2,3,4] before forcing the 5 out of the input list. Shall we leave it as an exercise?

这篇关于生成具有给定长度的组合的更快方法，保留顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！