A faster way of generating combinations with a given length, preserving the order

Question

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.

---

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

The list looks something like this

[f1, f2, f3 .. fn]

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

input : [f1, f2, f3 .. fn]

argument : 4 functions

output : A list of lists of 4 functions.

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

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.

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.

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:

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).

So what should I do?

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.

Answer 1

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

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.

Running:

> 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

Trying it:

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

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

---

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.

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]]

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