List of integers & L.I.S.

[Dan Sommers]

On 7 Sep 2005 09:48:52 -0700,
"n00m" <n00m at narod.ru> 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/>