Re: longuest interleaved sequences

[Jaroslav Hajek]

On Thu, May 20, 2010 at 5:41 PM, Judd Storrs <address@hidden> wrote:
> 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)]
>
>


Well, maybe I'm too tired today, but what about

 x = sort(rand(50,1)) ;
 y = sort(rand(54,1)) ;

[~, ix] = unique (lookup (y, x));
x = x(ix);
[~, iy] = unique (lookup (x, y));
y = y(iy);

and remove one element from the longer sequence if needed.


-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz