Find first 1 of the first sting of 1s who's length exceed the length of every subsequent string of 0s

Hi, I'm building a function to analyse american options and in the method I use I need to find or create an efficient algorithm that will analyse a vector made of ones and zeros and find the position of the first 1 of the first string of 1 which length exceeds the length of every subsequent string of 0. Example if the vector is v=[1,0,0,1,1,1,1,0,0,0,1,1,0,0,0,0,0,0,*1,1,1,0,0,1,1,1,1,0,0,1,0,1,1,1,1,1,1], the algorithm analysing the vector v should return the position of the *1...which is 19.

Anyone has any idea or knows commands that could help me?

Thank you Alex

Answer 1

[Matt Fig]

Here is a function which seems to always work, and is fast. I have had trouble with Walter's solution returning wrong results or erroring out for some v = round(rand(1,N));

function I = find_run_ones(v)
% Find the index of the beginning run of ones which is longer than any
% subsequent run of zeros.  Input arg must be a binary vector.
n = [true diff(v)~=0];
Lx = 1:length(v);  % Avoid FIND, hold the length of x.
x = v(n);  % x should be shorter than v.  Holds the numbers....
n = diff(Lx(n));  % Look at: [x; [n length(v)-sum(n)]] And the counts...
Lx = length(x);

if x(Lx)
    I = Lx;  % The return variable.
    zl = 0;  % The current highest number of consecutive zeros.
else
    I = 0;  % The index into n.
    zl = length(v) - sum(n);
end

for ii = Lx-1:-1:1
    if n(ii)>zl
        if x(ii)
            I = ii;
        else
            zl = n(ii);
        end
    end
end

if I
    I = sum(n(1:I-1))+1;
else
    I = [];
end

.

.

EDIT

I am unsure if you want a return index for the special case where the vector ends with ones. For example, v = [0 1 1 1] or v = [1 1 1]. In the first case do you want a 2 or an []? In the second case do you want a 1 or an []? My code currently returns a 2 and 1 respectively. To change it to the other output, replace this line:

I = Lx;  % The return variable.

with this:

I = 0;  % The return variable.

[Matt Fig]

I simplified some of the code...

[Alexandre]

Thanks!!!

Answer 2

[Walter Roberson]

Fractional answer that you might be able to flesh out:

>> reshape([find(~v,1)-1 diff(find(diff(v)))],2,[])
ans =
     1     4     2     3     4     1
     2     3     6     2     2     1

The upper row is the length of runs of 1's, the lower row is the length of runs of 0's that follow immediately thereafter.

Adjustments would have to be made for the case the array starts with 0 or ends in 0.

I can think of a way to test for the location you want using arrayfun() to do a hidden for loop, but perhaps when I've had some sleep I will think of a better way.

[Alexandre]

Thanks for the answer! In the meantime if your dreams bring you more answers please don't hesitate :)

[Walter Roberson]

For that sub-case

T = reshape([find(~v,1)-1 diff(find(diff(v)))],2,[]);

L = find(all( bsxfun(@gt,(1:size(T,2)).',1:size(T,2)) | bsxfun(@gt,T(1,:).', T(2,:)), 2),1);

P = 1 + sum(reshape(T(:,1:L-1),1,[]));

As mentioned above this would need to be tweaked for cases beginning or ending with 0.

The first bsxfun creates a lower-diagonal logical matrix. There might well be a better way (or at least a more readable way) to do that.

[Sean de Wolski]

tril(true(size(T)))

[Walter Roberson]

tril shouds like a good idea. It would have to be adjusted in this instance to

tril(true(size(T,2)),-1)

in order to exclude the diagonal.

[Alexandre]

Thx guys!! I've had to put this on hold because something else came up but I'm going to have with this next week...

Answer 3

[Andrei Bobrov]

use ideas of Walter Roberson and Matt Fig

v = v(:)';
ne = diff(find(diff([~v(1) v(:)' ~v(end)]))); % Walter Roberson
I = 1:length(v);
Ifirst = I([true diff(v)~=0]); % Matt Fig
tarr = v(Ifirst);
seq = find(tarr==1,1,'first'):find(tarr==0,1,'last');
ii = 1:2:length(seq);
logtlz = diff(ne(seq)) < 0;
Iof = Ifirst(seq(ii));
Iout = Iof(logtlz(ii));

My long variant

vt = [~v(1);v(:);~v(end)];
o = find(vt);
z = find(~vt);
nz = diff(o);
no = diff(z);
nz = nz(nz~=1)-1;
no = no(no~=1)-1;
t = length(no)-length(nz);
x = diff([[no;zeros(t<0)],[nz;zeros(t>0)]],[],2);
v1c = mat2cell(find(v(:)'),1,no);
Iout = cellfun(@(x)x(1),v1c(find((x(1:end-(t~=0|v(end)>0))<0))))

[Matt Fig]

Both of these solutions fail for certain cases. For example:

v = [0 1 0 0 0 1 1 1 1 0];

The first solution returns 3 (should be 6) and the second errors.

[Andrei Bobrov]

Thank you Matt, for your note ... adjusted ...

[Matt Fig]

Your welcome.

But now it returns multiple values:

V = [0 1 1 1 1 1 0 1 1 1]

[Andrei Bobrov]

Thanks, Matt ... I feel like Ovechkin in Vancouver in 2010 in the finals ... once corrected, sorry for the careless ...

[Matt Fig]

Getting closer!

V = [1 1 0 1 0 0 0 1 0 1]

I think your solution could be made to work! By the way, I am just doing this over and over:

V = round(rand(1,10))

find_run_ones(V) % MATT FIG

find_run_ones2(V) % ABOBROFF

About the only thing that is a little ambiguous to me is whether or not to say that a string ending in 1s counts for Alexandre. For example:

V = [0 1 1 1]

Do we return 2 or an empty matrix?? Oleg thinks an empty array is appropriate, whereas my current solution takes the latter approach.

[Andrei Bobrov]

I think empty matrix

[Matt Fig]

If so, then simply replacing this line in my code:

I = Lx; % The return variable.

with this:

I = 0; % The return variable.

will work force an [] to return.

Answer 4

[Oleg Komarov]

My solution with the aid of rude by Us

EDIT to take into account empty out for v = [0 1 1 1]

[len,val] = rude(v);
out = [];
for b = find(val)
    if len(b) > len(b+1:2:end)
        out = sum(len(1:b-1))+1
        return
    end
end

[Matt Fig]

It looks like the file by Us returns what I have for:

[x; [n length(v)-sum(n)]]

[Oleg Komarov]

Rude is just a run-length encoder/decoder. Basically I use it in order to avoid rewriting the algorithm all the time :)

Answer 5

[Alexandre]

Hey guys, To answer Matt, I need the answer to be 2 in the [0 1 1 1] case. You rock! I've been trying to figure out on my own for a while now, I should have come ask this question way before!!