Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
617 views
in Technique[技术] by (71.8m points)

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

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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?


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...