Re: longuest interleaved sequences

[Francesco Potortì]

>problem is as follows: given two ordered sequences x and y (x1 <= x2 <= ...
>xn; y1 <= y2 <= ym),
>extract the longuest subsequences xs and ys of the same length such that,
>for each element,
>x_i <= y_i <= x_{i+1}
>
>I have a few ideas, but if others already came with a fast and efficient
>algorithm, please share your thoughs.

The following steps could be ideas for starting.  I think one should
identify the longest sequences of ones in the two last vectors and
somehow match them with the x and y ordered sequences.

octave> L=100;N=16;x=y=1:L;for 
i=1:L-N;l=L+1-i;x(ceil(l*rand()))=[];y(ceil(l*rand()))=[];endfor;[x;y]
ans =

    6    8   10   26   31   44   45   50   58   64   70   74   77   82   84   88
    1    7   18   27   29   35   38   53   63   65   73   77   78   93   94   98

octave> [yy xx]=meshgrid(y,x); xx<=yy
ans =

   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
   0   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1
   0   0   1   1   1   1   1   1   1   1   1   1   1   1   1   1
   0   0   0   1   1   1   1   1   1   1   1   1   1   1   1   1
   0   0   0   0   0   1   1   1   1   1   1   1   1   1   1   1
   0   0   0   0   0   0   0   1   1   1   1   1   1   1   1   1
   0   0   0   0   0   0   0   1   1   1   1   1   1   1   1   1
   0   0   0   0   0   0   0   1   1   1   1   1   1   1   1   1
   0   0   0   0   0   0   0   0   1   1   1   1   1   1   1   1
   0   0   0   0   0   0   0   0   0   1   1   1   1   1   1   1
   0   0   0   0   0   0   0   0   0   0   1   1   1   1   1   1
   0   0   0   0   0   0   0   0   0   0   0   1   1   1   1   1
   0   0   0   0   0   0   0   0   0   0   0   1   1   1   1   1
   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   1
   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   1
   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   1


octave> diff(sum(xx<yy))
ans =

      1    2    1    0    1    0    3    1    1    1    1    1    3    0    0


octave> diff(sum(xx>=yy,2))'
ans =

      1    0    1    2    2    0    0    1    1    1    1    1    1    0    0

-- 
Francesco Potortì (ricercatore)        Voice: +39 050 315 3058 (op.2111)
ISTI - Area della ricerca CNR          Fax:   +39 050 315 2040
via G. Moruzzi 1, I-56124 Pisa         Email: address@hidden
(entrance 20, 1st floor, room C71)     Web:   http://fly.isti.cnr.it/