List of integers & L.I.S.

[n00m]

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?

[Dan Sommers]

On 7 Sep 2005 09:48:52 -0700,
"n00m" <n0**@narod.r u> 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.tombstoneze ro.net/dan/>

[manuelg]

I coded a solution that can compute the ordering numbers for
random.shuffle( range(1, 1000001)) in 2.5 seconds (typical, Win 2K Pro,
Pentium 4 2.40GHz 785Meg RAM)

Are you sure that this is not a homework problem?

[n00m]

Thanks guys!

Are you sure that this is not a homework problem? .... and let me reveal the secret:
http://spoj.sphere.pl/problems/SUPPER/

Hardly it can be easily reduced to "standard" LIS problem
(i.e. to find just a (any) Longest Increasing Sequence).
I coded a solution that can compute the ordering numbers for
random.shuffle( range(1, 1000001)) in 2.5 seconds (typical, Win 2K Pro,
Pentium 4 2.40GHz 785Meg RAM)

Sounds very impressive! It would be great to see your py solution got
accepted on my link (yes! they accept Python 2.4.1 solutions! and of
course the registration is free and fully anonymous).
So far there is no any accepted Py solution for this problem (see
link "Best Solutions" on the top of page of this problem).
Note: their machines are PIII Xeon 700MHz (no limit. for memory usage).

PS Thanks, Dan! but frankly speaking I'm not much interested just
to get someone's ready-to-use code without understanding how it
works.

[manuelg]

> ... and let me reveal the secret:

http://spoj.sphere.pl/problems /SUPPER/

your question is different than the question on this website.

also, what do you consider to be the correct output for this
permutation? (according to your original question)

[4, 5, 1, 2, 3, 6, 7, 8]

Manuel

[sp1d3rx]

So, this has no real world use, aside from posting it on a website.
Thanks for wasting our time. You are making up an arbitrary problem and
asking for a solution, simply because you want to look at the
solutions, not because your problem needs to be solved. Clearly, this
is a waste of time.

[manuelg]

Working on this allowed me to avoid some _real_ (boring) work at my
job.

So clearly it served a very useful purpose! ;)

Manuel

[Tim Peters]

[sp*****@gmail.c om]

So, this has no real world use, aside from posting it on a website.
Thanks for wasting our time. You are making up an arbitrary problem and
asking for a solution, simply because you want to look at the
solutions, not because your problem needs to be solved. Clearly, this
is a waste of time.

If investigating algorithms irritates you, ignore it. The people
writing papers on this topic don't feel it's a waste of time. For
example,

http://citeseer.ist.psu.edu/bespamya...umerating.html
"Enumeratin g Longest Increasing Subsequences and Patience Sorting (2000)"
Sergei Bespamyatnikh, Michael Segal

That's easy to follow, although their use of a Van Emde-Boas set as a
given hides the most challenging part (the "efficient data structure"
part).

[manuelg]

> That's easy to follow, although their use of a Van Emde-Boas set as a

given hides the most challenging part (the "efficient data structure"
part).
The "efficient data structure" is the easy part.

Obviously, it is a dict of lists.

....or is it a list of dicts?...

....or is it a tuple of generators?...

Anyway, "being aware of the literature", "thinking", "being smart", and
"being Tim Peters" are all forms of cheating.

I prefer not to cheat. ;)

nOOm, I still need an answer...
also, what do you consider to be the correct output for this
permutation? (according to your original question)

[4, 5, 1, 2, 3, 6, 7, 8]

Manuel

[n00m]

sp*****@gmail.c om wrote:

So, this has no real world use, aside from posting it on a website. I don't think you're quite right.
We never know where we gain and where we lose.
So clearly it served a very useful purpose! ;) Thanks, Manuel!
your question is different than the question on this website.

Not exactly so (maybe I'm wrong here). How I did it (but got TLE
- Time Limit Exceeded (which is 9 seconds)).

Firstly I find ordering numbers when moving from left to the right;
then I find ord. numbers for backward direction AND for DECREASING
subsequences:

4 5 1 2 3 6 7 8 << the list itself
1 2 1 2 3 4 5 6 << ordering numbers for forward direction
2 1 6 5 4 3 2 1 << ordering numbers for backward direction
===
3 3 7 7 7 7 7 7 << sums of the pairs of ord. numbers

Now those numbers with sum_of_ord.pair = max + 1 = 6 + 1
are the answer.
So the answer for your sample is: 1 2 3 6 7 8

Btw, I did it in Pascal. Honestly, I don't believe it can
be done in Python (of course I mean only the imposed time limit).
http://spoj.sphere.pl/status/SUPPER/