[EMAIL PROTECTED] wrote:
You have n elements, and you need to locate a specific k-element
permutation. There are n! / (n-k)! such permutations. You therefore
need log(n! / (n-k)!) bits of information.
A binary comparison provides one bit of information. So the number of
comparisons that
[EMAIL PROTECTED] wrote:
Quoting apfelmus [EMAIL PROTECTED]:
You mean O(k * log n + n) of course.
Erm, yes. You can do it in an imperative language by building a heap
in O(n) time followed by removing k elements, in O(k log n) time.
Ah, sorry, there are indeed to variants not comparable
For various reasons I had a similar problem that I solved iteratively
simply with a sorted list of the actual best elements.
The only particular things were
1. keep element count (to easily know if the element should be inserted
in any case)
2. keep the list in reverse order to have the
raghu vardhan [EMAIL PROTECTED]:
So, any algorithm that sorts is no good (think of n as huge, and k small).
With lazy evaluation, it is!
http://article.gmane.org/gmane.comp.lang.haskell.general/15010
[EMAIL PROTECTED] wrote:
The essence of all the answers that you've received is that it
Does the answer change if the data source isn't a list, already in memory,
but a stream? That is, will the sort end up pulling the entire stream into
memory, when we only need k elements from the entire stream.
Interestingly, this is almost exactly the same as one of my standard
interview
Ah, but which k elements? You won't know until you've drained your
entire stream!
Dan
Steve Downey wrote:
Does the answer change if the data source isn't a list, already in
memory, but a stream? That is, will the sort end up pulling the entire
stream into memory, when we only need k elements
Dan Weston [EMAIL PROTECTED] writes:
Ah, but which k elements? You won't know until you've drained your
entire stream!
True, but you still don't need to keep the whole stream in memory at
once, just the k-least-so-far as you work your way through the stream -
once you've read a part of the
Both Yitzchak's and my suggestions should run in constant space--some
strictness annotation or switching to foldl' might be necessary.
On 4/12/07, Mark T.B. Carroll [EMAIL PROTECTED] wrote:
Dan Weston [EMAIL PROTECTED] writes:
Ah, but which k elements? You won't know until you've drained your
G'day all.
Quoting apfelmus [EMAIL PROTECTED]:
You mean O(k * log n + n) of course.
Erm, yes. You can do it in an imperative language by building a heap
in O(n) time followed by removing k elements, in O(k log n) time.
Cheers,
Andrew Bromage
___
