Re: Looking for a fast algorithm
- From: Ben Rudiak-Gould <br276deleteme@xxxxxxxxx>
- Date: Mon, 16 Jan 2006 17:54:02 +0000
frederik_coppens@xxxxxxxxx wrote:
Now, it's possible to make sequences of objects by taking an object from every row, and to associate a number with each such sequence by multiplying the numbers of every object. It's clear that the sequence with the highest number will be the one obtained by taking the first object of every row. But how do I find the X highest sequences?
I have no idea if this is optimal, but here's how I'd do it:
For one row the problem is trivial. For n+1 rows, recursively calculate the stream (lazy list) of highest-to-lowest sequences for all rows but the first; then multiply that stream by the k different object values from the first row, obtaining k streams; then compute the merge of those streams. A quick mental calculation suggests that taking the first X elements of the result will cost O(X log (k1 k2 ... kn)) steps, which looks reasonable, since with X = k1 k2 ... kn it matches the cost of the obvious approach of pregenerating all the sequences and sorting them.
-- Ben .
- References:
- Looking for a fast algorithm
- From: frederik_coppens
- Looking for a fast algorithm
- Prev by Date: Looking for a fast algorithm
- Next by Date: Help!! Random Integer Generator Algorithm
- Previous by thread: Looking for a fast algorithm
- Next by thread: Re: Looking for a fast algorithm
- Index(es):
Relevant Pages
|
