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 To: raghu vardhan 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/