There seems to be some confusion about the question. There are two key things
to keep in mind here:
1) You must make at most O(k*n) comparisons (in the worst case) if the list has
length n.
2) The output must be the indices and not the numbers themselves.
So, any algorithm that sorts is no good (think of n as huge, and k small).
Another interesting caveat to this is that if k=2, you can actually solve the
problem with just (n+log n) comparisons in worst case(instead of 2*n, that you
get by a naive approach), and it's a nice exercise to do this.
As a further clarification, this is not a homework question. I genereally do
whatever programming I do in Matlab, as I work with matrices (huge ones) and
use this function a lot. I just wanted to see how different an implementation
you can get in Haskell (I am new to Haskell so I might not be able to come up
with the best way to do this).
----- Original Message ----
From: Stefan O'Rear <[EMAIL PROTECTED]>
To: raghu vardhan <[EMAIL PROTECTED]>
Cc: [EMAIL PROTECTED]
Sent: Wednesday, 11 April, 2007 10:47:08 PM
Subject: Re: [Haskell-cafe] k-minima in Haskell
On Wed, Apr 11, 2007 at 08:38:48PM -0700, Stefan O'Rear wrote:
> On Thu, Apr 12, 2007 at 08:58:33AM +0530, raghu vardhan wrote:
> > What's the best way to implement the following function in haskell:
> > Given a list and an integer k as input return the indices of the least
> > k elements in the list. The code should be elegant and also, more
> > importantly, must not make more than the minimum O(k*length(list))
> > number of operations.
>
> Go read and thoroughly understand "Why Functional Programming
> Matters."
>
> Also, your asyptotic complexity bound is just plain wrong. I'd give
> faster code, but Don is suspicious (and I can never tell these things
> myself).
>
> Stefan
Don tells me (in #haskell) that you are legitimate, so here is the
example:
kminima k lst = take k $ sort lst
If you want to be really explicit about it, here is a sort that will
work:
sort [] = []
sort l@(x:_) = filter (<x) l ++ filter (==x) l ++ filter (>x) l
(A stable quicksort, btw)
Note that this is FASTER than your bound - somewhere between O(n) and
O(n*log n).
Ain't lazy evaluation great? :)
Stefan
Send a FREE SMS to your friend's mobile from Yahoo! Messenger. Get it now
at http://in.messenger.yahoo.com/_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
