Re: longuest interleaved sequences

[Judd Storrs]

On Thu, May 20, 2010 at 10:23 AM, CdeMills <address@hidden> wrote:
>
> Hello,
>
> 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}

This is an interesting problem. I'm not sure I completely understood.
My confusion relates to the case that n != m and the use of i on both
x_i and y_i.  I assume that you really just want sequential elements
of x and y to interleave but that you don't actually care that the
sequences are located at the same position in x and y or whether the
sequence starts with x or y. i.e. something more like

... x_i <= y_j <= x_{i+1} <= y_{j+1} ...

This is what I came up with. The major problem with my solution is
that the key sort of the pooled x and y, if there are any x_i == y_j
it doesn't try both orders and just uses whatever sort() puts out.

## Create random input vectors
x = sort(rand(50,1)) ;
y = sort(rand(54,1)) ;

nx = numel(x) ;
ny = numel(y) ;

## Sort all elements. Note: problem with ties in x and y.
[z,idx] = sort([x;y]) ;

## Compute mask: 0=from x; 1=from y
pat = idx > nx ;

## Now need to find longest alternating series
## { 0 1 0 1 0 1 0 1 ... } or { 1 0 1 0 1 0 1 ... }
##
## i i+1
## 0 1   => i and i+1 are candidates
## 0 0   => i+1 breaks sequence
## 1 0   => i and i+1 are candidates
## 1 1   => i+1 breaks sequence
brk = pat ;
brk(2:end) = ! xor(pat(1:end-1), pat(2:end)) ;

## Label each sequence by integration
lab = cumsum(brk) ;

## Count sequence lengths
len = histc(lab,0:lab(end)) ;

## Find longest
[lmax,imax] = max(len) ;

## Positions within sorted list of all elements
idx2 = idx(lab == imax-1) ;

ix = idx2(idx2<=nx) ;
iy = idx2(idx2>nx)-nx ;

[ix, x(ix)]
[iy, y(iy)]




--judd