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

问题描述

TL; DR :我希望确切的行为为filter ((== 4) . length) . subsequences.仅使用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 -> 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个功能

output: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，然后再取一个n-1，则取自xs；否则我们不使用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屋！