Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Combinations of choosing n items from a list (Peter Hall)
2. Re: Combinations of choosing n items from a list (Daniel Fischer)
3. Re: Combinations of choosing n items from a list (Peter Hall)
----------------------------------------------------------------------
Message: 1
Date: Sun, 13 Nov 2011 22:42:25 +0000
From: Peter Hall <[email protected]>
Subject: [Haskell-beginners] Combinations of choosing n items from a
list
To: [email protected]
Message-ID:
<CAA6hAk716Nq-vc-R2bFuO=gP_zcsFz4pZz1n_fVx+=tzeou...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
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
------------------------------
Message: 2
Date: Mon, 14 Nov 2011 01:13:11 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Combinations of choosing n items from
a list
To: [email protected], [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="iso-8859-1"
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
------------------------------
Message: 3
Date: Mon, 14 Nov 2011 00:53:52 +0000
From: Peter Hall <[email protected]>
Subject: Re: [Haskell-beginners] Combinations of choosing n items from
a list
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID:
<CAA6hAk5_zGjywQLhNemAPjik92_KzXnBUj9omUGwex=31k5...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
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
<[email protected]> 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
>
>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 41, Issue 19
*****************************************
