Re: Looking for a fast algorithm

In article <1137421964.191059.71720@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
frederik_coppens@xxxxxxxxx says...
> Hi,
>
> 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?

I would say no. This sort of combinatorial problem is inevitably NP.
(It's quite similar to the one posed recently of finding the N shortest
paths on a graph.)

Thre will be no 'key' that allows you to summarise the relevant
combinations. Therefore the number you need to assess will increase
exponentially.

- Gerry Quinn
.

Relevant Pages

  • Re: Fasctode - Sort estimating complexity and B&V
    ... executed and measurest by all algorithm. ... execution time) for these sequences. ... be a Borland function, ... sort ever eneter in O. ...
    (borland.public.delphi.language.basm)
  • Re: for x,y > 7 twins(x+y) <= twins(x) + twins(y)
    ... That would be odd, since you have declared ... proof consists of our having at hand a list of sequences of ones and ... zeros -- ones and zeros wonderfully agreeing to come one after other, ... the whole sentence an uncanny, eerie, quaint sort of air -- or, so to ...
    (sci.math)
  • Re: Using hashes to sort number sequences
    ... > and search for similar number sequences in file b.txt. ... Why don't you just sort (using the Unix or maybe even the Win32 sort ... of method will avoid reading your $infile2 many ... You are discarding that data, ...
    (comp.lang.perl.misc)
  • Re: Listening to music can prompt the brain to send positive signals throughout the body
    ... people are following along with these sequences of tones, ... some sort of craving and a need to hear the next note, ...
    (rec.music.makers.guitar.acoustic)
  • Re: Using hashes to sort number sequences
    ... > Martin Foster wrote: ... I may need to tell you a little more about the data, I'm not sure a sort ... one can compare the coordination sequences (the number ... > outer loop. ...
    (comp.lang.perl.misc)