Combinations of choosing n items from a list

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Combinations of choosing n items from a list

Peter Hall
Hi all,
This function took me a long time to write, getting my head around the
double recursion. It returns a list of all possible sub-sets of a
given length from a list.

I have a couple of questions.

1. Can it be improved for efficiency or style?
2. Is there a library that already has this and other related
functions? I assumed there would be but I couldn't find it on hoogle.


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

e.g.
> combinations 3 [1..5]
[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]

Thanks,
Peter


Reply | Threaded
Open this post in threaded view
|

Combinations of choosing n items from a list

Daniel Fischer
On Sunday 13 November 2011, 23:42:25, Peter Hall wrote:

> Hi all,
> This function took me a long time to write, getting my head around the
> double recursion. It returns a list of all possible sub-sets of a
> given length from a list.
>
> I have a couple of questions.
>
> 1. Can it be improved for efficiency or style?
> 2. Is there a library that already has this and other related
> functions? I assumed there would be but I couldn't find it on hoogle.
>
>
> combinations :: Int -> [a] -> [[a]]
> combinations _ [] = []
> combinations 0 _ = []

That should be

combinations 0 _ = [[]]

since there is one sublist of length 0 of any list.
And that equation should come before

combinations _ [] = []

> combinations 1 x = map (:[]) x

This equation is then superfluous.

> combinations n (x:xs) = (map (x:) $ combinations (n-1) xs) ++
> combinations n xs

Some would prefer a list-comprehension here,

combinations n (x:xs)
    = [x:comb | comb <- combinations (n-1) xs]
       ++ combinations n xs

(indentation to prevent wrapping in mail-clients),
but I would leave the decision to personal preference (well, I would use a
list-comprehension, but I've no pains with the map. However, I submit also
  map (x:) (combinations (n-1) xs) ++ combinations n xs
for consideration).

As for efficiency, yes, there's something you can do to dramatically
improve performance, if you don't want to treat infinite lists (as it is,
you'd only get sublists with identical (n-1)-long initial segment anyway,
so support for infinite lists isn't ideal).

Consider for example

combinations 25 [1 .. 25]
~> [1:c | c <- ([2:d | d <- combinations 23 [3 .. 25]]
                             ++ combinations 24 [3 .. 25])]
         ++ combinations 25 [2 .. 25]

For the second part, you go through all 2^24 sublists of [2 .. 25], only to
find that all of them are too short. In the second part of the first part,
you go through all 2^23 sublists of [3 .. 25] to find all of them too
short.
Continuing the splitting, you see that

combinations 25 [1 .. 25]

goes through all 2^25 sublists of [1 .. 25], finding all of them where an
element was discarded anywhere too short.
A lot of wasted work.

If n > length xs, you know that xs has no sublists of length n, so you can
abort the calculation immediately. Since calculating the length requires
traversing the entire list, we'd rather not do that at each step, but carry
the length as a parameter.

combinations 0 _ = [[]]
combinations _ [] = []
combinations n xs
  | n < 0     = []
  | n == 1    = map (:[]) xs  -- not needed, but a wee bit more efficient
  | otherwise = helper n (length xs) xs
    where
      helper k l ys@(z:zs)
        | k < l     = [z:ws | ws <- helper (k-1) (l-1) zs]
                          ++ helper k (l-1) zs
        | k == l    = [ys]
        | otherwise = []   -- can only occur at the start

Not so nice, but avoids a lot of futile work.
The call to length prohibits infinite lists. You could, at some cost, treat
infinite lists per

combinations 0 _ = [[]]
combinations _ [] = []
combinations n xs@(y:ys)
  | n < 0     = []
  | otherwise = case drop (n-1) xs of
                  [ ] -> []
                  [_] -> [xs]
                  _   -> [y:c | c <- combinations (n-1) ys]
                            ++ combinations n ys

to get the same result as before for infinite lists. The finite case would
be slower than the previous with the helper and length, but still avoid
most of the futile work when n is close to length xs.

>
> e.g.
>
> > combinations 3 [1..5]
>
> [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5]
> ,[3,4,5]]
>
> Thanks,
> Peter



Reply | Threaded
Open this post in threaded view
|

Combinations of choosing n items from a list

Peter Hall
Thanks for the detailed response! I'll be digesting it properly over
the next few days.

Peter


On Mon, Nov 14, 2011 at 12:13 AM, Daniel Fischer
<daniel.is.fischer at googlemail.com> wrote:

> On Sunday 13 November 2011, 23:42:25, Peter Hall wrote:
>> Hi all,
>> This function took me a long time to write, getting my head around the
>> double recursion. It returns a list of all possible sub-sets of a
>> given length from a list.
>>
>> I have a couple of questions.
>>
>> 1. Can it be improved for efficiency or style?
>> 2. Is there a library that already has this and other related
>> functions? I assumed there would be but I couldn't find it on hoogle.
>>
>>
>> combinations :: Int -> [a] -> [[a]]
>> combinations _ [] = []
>> combinations 0 _ = []
>
> That should be
>
> combinations 0 _ = [[]]
>
> since there is one sublist of length 0 of any list.
> And that equation should come before
>
> combinations _ [] = []
>
>> combinations 1 x = map (:[]) x
>
> This equation is then superfluous.
>
>> combinations n (x:xs) = (map (x:) $ combinations (n-1) xs) ++
>> combinations n xs
>
> Some would prefer a list-comprehension here,
>
> combinations n (x:xs)
> ? ?= [x:comb | comb <- combinations (n-1) xs]
> ? ? ? ++ combinations n xs
>
> (indentation to prevent wrapping in mail-clients),
> but I would leave the decision to personal preference (well, I would use a
> list-comprehension, but I've no pains with the map. However, I submit also
> ?map (x:) (combinations (n-1) xs) ++ combinations n xs
> for consideration).
>
> As for efficiency, yes, there's something you can do to dramatically
> improve performance, if you don't want to treat infinite lists (as it is,
> you'd only get sublists with identical (n-1)-long initial segment anyway,
> so support for infinite lists isn't ideal).
>
> Consider for example
>
> combinations 25 [1 .. 25]
> ~> [1:c | c <- ([2:d | d <- combinations 23 [3 .. 25]]
> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ++ combinations 24 [3 .. 25])]
> ? ? ? ? ++ combinations 25 [2 .. 25]
>
> For the second part, you go through all 2^24 sublists of [2 .. 25], only to
> find that all of them are too short. In the second part of the first part,
> you go through all 2^23 sublists of [3 .. 25] to find all of them too
> short.
> Continuing the splitting, you see that
>
> combinations 25 [1 .. 25]
>
> goes through all 2^25 sublists of [1 .. 25], finding all of them where an
> element was discarded anywhere too short.
> A lot of wasted work.
>
> If n > length xs, you know that xs has no sublists of length n, so you can
> abort the calculation immediately. Since calculating the length requires
> traversing the entire list, we'd rather not do that at each step, but carry
> the length as a parameter.
>
> combinations 0 _ = [[]]
> combinations _ [] = []
> combinations n xs
> ?| n < 0 ? ? = []
> ?| n == 1 ? ?= map (:[]) xs ?-- not needed, but a wee bit more efficient
> ?| otherwise = helper n (length xs) xs
> ? ?where
> ? ? ?helper k l ys@(z:zs)
> ? ? ? ?| k < l ? ? = [z:ws | ws <- helper (k-1) (l-1) zs]
> ? ? ? ? ? ? ? ? ? ? ? ? ?++ helper k (l-1) zs
> ? ? ? ?| k == l ? ?= [ys]
> ? ? ? ?| otherwise = [] ? -- can only occur at the start
>
> Not so nice, but avoids a lot of futile work.
> The call to length prohibits infinite lists. You could, at some cost, treat
> infinite lists per
>
> combinations 0 _ = [[]]
> combinations _ [] = []
> combinations n xs@(y:ys)
> ?| n < 0 ? ? = []
> ?| otherwise = case drop (n-1) xs of
> ? ? ? ? ? ? ? ? ?[ ] -> []
> ? ? ? ? ? ? ? ? ?[_] -> [xs]
> ? ? ? ? ? ? ? ? ?_ ? -> [y:c | c <- combinations (n-1) ys]
> ? ? ? ? ? ? ? ? ? ? ? ? ? ?++ combinations n ys
>
> to get the same result as before for infinite lists. The finite case would
> be slower than the previous with the helper and length, but still avoid
> most of the futile work when n is close to length xs.
>
>>
>> e.g.
>>
>> > combinations 3 [1..5]
>>
>> [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5]
>> ,[3,4,5]]
>>
>> Thanks,
>> Peter
>
>


Reply | Threaded
Open this post in threaded view
|

Combinations of choosing n items from a list

Lorenzo Bolla
In reply to this post by Peter Hall
What about something like:

combinations n = filter (\s -> length s == n) . subsequences

hth,
L.



On Sun, Nov 13, 2011 at 10:42 PM, Peter Hall <peter.hall at memorphic.com>wrote:

> Hi all,
> This function took me a long time to write, getting my head around the
> double recursion. It returns a list of all possible sub-sets of a
> given length from a list.
>
> I have a couple of questions.
>
> 1. Can it be improved for efficiency or style?
> 2. Is there a library that already has this and other related
> functions? I assumed there would be but I couldn't find it on hoogle.
>
>
> combinations :: Int -> [a] -> [[a]]
> combinations _ [] = []
> combinations 0 _ = []
> combinations 1 x = map (:[]) x
> combinations n (x:xs) = (map (x:) $ combinations (n-1) xs) ++ combinations
> n xs
>
> e.g.
> > combinations 3 [1..5]
>
> [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
>
> Thanks,
> Peter
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20111114/78658a4f/attachment.htm>