[Haskell-cafe] k-minima in Haskell

[raghu vardhan]

And just to remind people, the question is to find the indices and not
the numbers themselves. For example on input '3, [10,9,8,..., 3,2,1]'
the output must be '[9,8,7]'. 

----- Original Message ----
From: Stefan O'Rear <stefanor at cox.net>
To: raghu vardhan <mrvr84 at yahoo.co.in>
Sent: Wednesday, 11 April, 2007 11:17:15 PM
Subject: Re: [Haskell-cafe] k-minima in Haskell

On Thu, Apr 12, 2007 at 09:30:22AM +0530, raghu vardhan wrote:
> Hmmm.  That's not something I was looking for. I'm not sure the
> running time is good enough (think of k as being 2 - then you should
> not make more than 2n comparisons) - even with lazy evaluation,
> quick sort won't have a bound of O(k*n). 

Muahahahaha!
Muahahahahahahahahahaha!
Muahaha!

Actually it DOES.

(this list courtesy of a ghci one-liner)

find the 3 minima of [71,71,17,14,16,91,18,71,58,75,65,79,76,18,4,45,87,51,93,36]

============

take 3 (sort [71,71,17,14,16,91,18,71,58,75,65,79,76,18,4,45,87,51,93,36])

vvvvvvvvvvvv

take 3 (sort (filter (<71) [71,71,17,14,16,91,18,71,58,75,65,79,76,18,4,45,87,51,93,36]) ++ a bunch of stuff I won't track because it won't be evaluated)

vvvvvvvvvvvv  (comparisons so far: 20)

take 3 (sort [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36])

take 3 (sort (filter (<17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]) ++ 
        filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
        sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))

vvvvvvvvvvvv (31)

take 3 (sort [14, 16, 18, 4] ++ 
        filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
        sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))

take 3 (sort (filter (<14) [14, 16, 18, 4]) ++ sort (filter (==14) [14, 16, 18, 4]) ++ sort (filter (>14) [14, 16, 18, 4]) ++ 
        filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
        sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))

vvvvvvvvvvvv (39)

take 3 (sort [4] ++ sort [14] ++ sort (filter (>14) [14, 16, 18, 4]) ++ 
        filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
        sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))

take 3 (4 : 14 : sort (filter (>14) [14, 16, 18, 4]) ++ 
        filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
        sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))

4 : 14 : take 1 (sort (filter (>14) [14, 16, 18, 4]) ++ 
        filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
        sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))

vvvvvvvvvvvv (43)

4 : 14 : take 1 (sort [16, 18] ++ 
        filter (==17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36] ++
        sort (filter (>17) [17, 14, 16, 18, 58, 65, 18, 4, 45, 51, 36]))

vvvvvvvvvvvv (47)

[4, 14, 16]

47 close enough to O(n*k) for you?  (remember this is quicksort we are
dealing with, O(n^2) worst case)

Stefan







      Send a FREE SMS to your friend's mobile from Yahoo! Messenger. Get it now at http://in.messenger.yahoo.com/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070412/02d747c8/attachment.htm