Re: Looking for a fast algorithm


frederik_coppens@xxxxxxxxx wrote:
> I have the following problem. I have rows of objects, each if which is
> associated with a number. The rows are of different length. The objects
> on each row are sorted, the objects with the highest numbers come
> first.
> 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? (ie the
> X sequences with the highest numbers, where X can be for example 100.)
> It's of course possible with brute force search, but Is there a fast
> algorithm for doing this?
> Thanks,

Observe that after the first sequence, each new sequence will be
different in only row from some previously selected sequence. If
multiplication/division is O(1), and you have k rows, you can find the
top X sequences in O(Xk log(Xk)) time.

My statement, and your 'it's clear' statement both assume that
a>=b,c>=d implies ac>=bd, which puts some restrictions on the numbers.

.

Relevant Pages

  • Re: The last ancestor of all life
    ... that a specific sequence will exist in a given genome. ... terminology of probability theory. ... multiplying probabilities is the way to go here. ... However, at higher and higher levels, the size ...
    (talk.origins)
  • Re: The last ancestor of all life
    ... that a specific sequence will exist in a given genome. ... terminology of probability theory. ... multiplying probabilities is the way to go here. ... the proteins' P, P, P, etc. ...
    (talk.origins)
  • Re: Hilbert transform using FFT approach
    ... Multiplying any sequence that has zeros with another equal length ... sequence will have zeros in the same locations and may introduce more. ... Are you talking about a combined mix by Fs/4 and decimate by 4 filter? ...
    (comp.dsp)
  • Re: iterative-version for computing a Fibonacci number
    ... if you keep multiplying A by itself you get the following sequence: ... You will notice that the sequence of first numbers from each matrix is ... the Fibonacci sequence. ... This technique is used in the Python code here: ...
    (comp.lang.lisp)
  • Different Color
    ... And if and other sequence id found on that row to assign another color. ... Then to check and assign the next row until the range is empty. ... My question above rests on two of the same colors. ... Prev by Date: ...
    (microsoft.public.excel.programming)