On 7 Sep 2005 09:48:52 -0700,
"n00m" <[EMAIL PROTECTED]> wrote:
> Given a list of N arbitrarily permutated integers from set {1..N}.
> Need to find the ordering numbers of each integer in the LONGEST
> increasing sequence to which this number belongs. Sample:
> List:
> [4, 5, 6, 1, 2, 7, 3]
> Corresponding ordering numbers:
> [1, 2, 3, 1, 2, 4, 3]
> Details:
> e.g. number 7 belongs to increasing sequence 1, 2, 7; but this
> sequence is not the LONGEST sequence for "7". The longest sequence
> for the 7 is 4, 5, 6, 7. So, the 7's ordering number in this sequence
> is 4.
> The salt of the thing is to do this with an O(n*log(n)) algorithm!
> The straightforward O(n^2) algorithm is toooo slooow.
> Any ideas?
I wrote something like that for the Discrete Mathematics I took last
spring (we had to produce the longest sequence, though, rather than the
indexes into the original list, our list was not necessarily a
permutation of 1..N, and I "cheated" on the longest descending sequnce
by changing one of the comparison operators and re-running the program).
If push comes to shove, I suppose I could post the whole program (all
100 lines of it), but here's the comment near the top:
# consider that there are 2 ** n subsequences (corresponding to the 2 **
# n permutations of the original sequence); the trick is to accumulate
# them all at once while skipping the ones that are not strictly
# ascending and also pruning sequences that obviously can't "win"
It's not much to go on, but that bit after the ";" is the algorithm I
use. I can't tell you how fast it runs in big-O notation, but my old
500 MHz PowerMac G4 digested lists of tens or hundreds of thousands of
random integers while I waited.
Regards,
Dan
--
Dan Sommers
<http://www.tombstonezero.net/dan/>
--
http://mail.python.org/mailman/listinfo/python-list
