Extract largest sequence w/o Brute Force

[ihatehippies]

Can anyone think of an intelligent way to extract the largest sequence of numbers from a list like:

[[2, 4, 9], [3, 5, 10], [6], [2, 4, 9], [1, 8, 11], [3, 5, 10], [6], [2, 4, 9], [0, 7], [1, 8, 11]]

without brute forcing every possibility.

You can only use one number from each nested list and you have to move forward down the main list. ie you could use the '2' from nested list one and the '3' from nested list two. You could use the '6' from nested list 3, but that would limit you to using the '9' from nested list four. So on and so forth.
I've been trying to think of a set of rules that would drastically reduce the number of possibilities that my program would have to check in order to retrieve the longest sequence.

[TrustyTony]

Do you need to take from every list? 6 is only number in two lists. Why can not take 4 from third list?

[ihatehippies]

No, you do not need to take a number from every list. In that example if you used the '6' you wouldn't be able to use the '4' from the next list b/c 6>4.

[woooee]

It helps to look at this pictorially.

0  1  2  3  4  5  6  7  8  9  10 11  <===== number in the list

      1*    1              1     
  
         2*    2              2  
  
                  3              
  
      4     4*             4     
  
   5                    5        5  
 
         6     6*             6  
  
                  7*             
  
      8     8              8*    
  
9                    9*          
  
   10                   10*       11*

So the longest chain would be 1-2-4-6-7-9-10 = "2" from first list, "3" from 2nd list, "4" from 4th list, etc
or 1-2-4-6-7-8-11
A linked list variation would probably work with the longest chain being having the most links.

[TrustyTony]

Here is the brute force to check with, first of all ( I assume not repeating of value allowed, each bigger than previous):

import itertools
listnum = [[2, 4, 9], [3, 5, 10], [6], [2, 4, 9], [1, 8, 11], [3, 5, 10], [6], [2, 4, 9], [0, 7], [1, 8, 11]]
listnumN= [x+[None] for x in listnum]

res = []
for i in itertools.product(*listnumN):
    small=i[0]
    for x in i[1:]:
        if x and x <= small: break
        elif x: small=x
    else:
        r = [ x for x in enumerate(i) if x[1]]
##        print 'Found:',r
        res.append(r)
m = max(res,key=len)
print 'Max: ',m,', length:', len(m)  
"""Output:
Max:  [(0, 2), (1, 3), (3, 4), (5, 5), (6, 6), (7, 9), (9, 11)] , length: 7
"""

[TrustyTony]

Still one post against thread title, sorry.

Here still brute force which shows all possible alternatives for longest and storing only the longest length candidates:

import itertools
import pretty ## see my code snippet
listnum = [[2, 4, 9], [3, 5, 10], [6], [2, 4, 9], [1, 8, 11], [3, 5, 10], [6], [2, 4, 9], [0, 7], [1, 8, 11]]
listnumN= [x+[None] for x in listnum]

res = []
lr=0

for i in itertools.product(*listnumN):
    small=i[0]
    for x in i[1:]:
        if x and x <= small: break
        elif x: small=x
    else:
        r = [ x for x in enumerate(i) if x[1] ]
##        print 'Found:',r
        if (not res) or (len(r)>lr):
              res=[r]
              lr=len(r)
##              print lr,
        elif len(r) == lr and r not in res:
            res.append(r)

print 'Max lists: ',pretty.mypr(res),', length:', lr  
"""Output:
Max lists:  
[
  [
    (0, 2), 
    (1, 3), 
    (3, 4), 
    (5, 5), 
    (6, 6), 
    (7, 9), 
    (9, 11)], 
  [
    (0, 2), 
    (1, 3), 
    (3, 4), 
    (5, 5), 
    (6, 6), 
    (8, 7), 
    (9, 8)], 
  [
    (0, 2), 
    (1, 3), 
    (3, 4), 
    (5, 5), 
    (6, 6), 
    (8, 7), 
    (9, 11)]] , length: 7
"""

[ihatehippies]

**reading about linked lists

[TrustyTony]

Maybe should read about trees (of course can implement as linked list).

The problem in my mind is that in order to build decision tree and search it for sorted sequences, is maybe more heavy operation than generate and test, fail fast version I gave for testing and timing solutions against.