How many consecutive ones?

Write a function ConsecutiveOnes to detect in a logical row array of any length the locations the length of the ones sequences. If there is a single one, the location of the one should be indicated with a length of one. For example, for the input array [0 0 1 1 0 0 1] the function ConsecutiveOnes produces the output [0 0 2 0 0 0 1]; for the input array [0,0,1,1,0,0,0,1,1,1] the function ConsecutiveOnes produces the output [0 0 2 0 0 0 0 3 0 0]

I am trying a recursion function, which should be sth like

for i = 1:a
function indicator = solve(inputArray1(i))

I know this expression is wrong, but I wonder how to display an idea like this.

[Jan]

I do not understand the intention of these 2 lines of code. A recursive function is possible, but much more complicated then needed.

You got this homework to learn how to solve such problems. Then it would not be useful, if the solution is posted in the forum. Try it with a loop.

[Zhuoyi Chen]

Yeah, I know that, but I did try. Also, I am here to ask for a method, not an answer. For my first attempt, I tried the following code.

    a = length(inputArray);
    indicator = zeros(1,a)

        for i = 1:(a-1)
            if (inputArray(i) == 1)&(inputArray(i+1) ==1)
                indicator(i) = indicator(i) + 1
                n = i+1
                while n<=a
                    if inputArray(n) == 0
                        break
                    end 
                        indicator(i) = indicator(i) +1
                        n = n+1
                end
                    inputArray((i+1):n) = 0;
            end
        end

It works for [0,0,1,1,0,0,0,1,1,1] actually, but it fails to [0, 1, 1, 0, 1].

Answer 1

[Andrei Bobrov]

out = double(diff([~A(1);A(:)]) == 1);
v = accumarray(cumsum(out).*A(:)+1,1);
out(out == 1) = v(2:end);

or

out = zeros(size(A));
ii = strfind([0,A(:)'],[0 1]);
out(ii) = strfind([A(:)',0],[1 0]) - ii + 1;

[Zhuoyi Chen]

Thanks for posting! I will try it!

[Zhuoyi Chen]

Okey, that is a super clever way to solve it.... LOL THANK YOU SO MUCH!

[Jan]

@Andrei: As usual I've measured the timings. The STRFIND method is the fastest: +1 for this solution.

It is 10% faster if the padded array is created once only. This matters especially for large inputs, which do not match into the processor cache:

out     = zeros(size(a));
aa      = [0,a,0];
ii      = strfind(aa, [0 1]);
out(ii) = strfind(aa, [1 0]) - ii;

[Andrei Bobrov]

Thank you Jan!

[Image Analyst]

Please start a new thread on this (not here).

Answer 2

[Jan]

I'd start at the end of the vector and store the value. Then run a loop from length(a)-1 to 1. If the corresponding element is 0, the value of c is written to the element on the right and c is set to 0. If it is 1, c is increased by 1. After the loop the last value of c is written to the first element of the output.

a = [0,0,1,1,0,0,0,1,1,1];

c = a(end);
for k = length(a)-1:-1:1
  if a(k) == 0
    a(k+1) = c;
    c      = 0;
  else
    a(k+1) = 0;
    c      = c + 1;
  end
end
a(1) = c;

Or the same with multiplications instead of the IF branches:

a = [0,0,1,1,0,0,0,1,1,1];

c = a(end);
for k = length(a)-1:-1:1
  a(k+1) = c * (1 - a(k));
  c      = a(k) * (c + 1);
end
a(1) = c;

Well, this is ugly. Without good comments, it will take a while until its intention gets clear.

In productive code a vectorized method would be the best idea:

k    = find([true, diff(a) ~= 0]);      % Indices of changed values
r    = zeros(size(a));
r(k) = a(k) .* diff([k, length(a)+1]);  % Distance of changes

[Zhuoyi Chen]

Thanks for posting!

[Zhuoyi Chen]

Well... while running your first method. I got [0 0 2 0 0 0 0 3 0 1] instead of [0 0 2 0 0 0 0 3 0 0] in the case of [0,0,1,1,0,0,0,1,1,1]. I suggested that something might go wrong....

[Jan]

Problem is fixed.

[Jan]

As usual some timings:

function neatoTest
a = randi([0,1], 1, 1e6);

tic; for k = 1:20, r = Accum(a); end; toc
tic; for k = 1:20, r = Strfind1(a); end; toc
tic; for k = 1:20, r = Strfind2(a); end; toc
tic; for k = 1:20, r = Loop1(a); end; toc
tic; for k = 1:20, r = Loop2(a); end; toc
tic; for k = 1:20, r = Find1(a); end; toc
end

function out = Accum(a)
out = double(diff([~a(1);a(:)]) == 1);
v = accumarray(cumsum(out).*a(:)+1,1);
out(out == 1) = v(2:end);
end

function out = Strfind1(a)
out = zeros(size(a));
ii = strfind([0,a(:)'],[0 1]);
out(ii) = strfind([a(:)',0],[1 0]) - ii + 1;
end

function out = Strfind2(a)
out     = zeros(size(a));
aa      = [0,a,0];
ii      = strfind(aa, [0 1]);
out(ii) = strfind(aa, [1 0]) - ii;
end

function a = Loop1(a)
c = a(end);
for k = length(a)-1:-1:1
  if a(k) == 0
    a(k+1) = c;
    c      = 0;
  else
    a(k+1) = 0;
    c      = c + 1;
  end
end
a(1) = c;
end

function a = Loop2(a)
c = a(end);
for k = length(a)-1:-1:1
  a(k+1) = c * (1 - a(k));
  c      = a(k) * (c + 1);
end
a(1) = c;
end

function r = Find1(a)
k    = find([true, diff(a) ~= 0]);      % Indices of changed values
r    = zeros(size(a));
r(k) = a(k) .* diff([k, length(a)+1]);  % Distance of changes
end

Results (R2009a, Win64):

 Elapsed time is 0.873261 seconds.  Andrei Accumarray
 Elapsed time is 0.601190 seconds.  Andrei strfind
 Elapsed time is 0.532654 seconds.  Andrei strfind + [0,a,0]
 Elapsed time is 1.053366 seconds.  Jan loop
 Elapsed time is 0.956481 seconds.  Jan ugly loop
 Elapsed time is 0.709494 seconds.  Jan vectorized

The best vectorized solution is two times faster than the loop. But loops are not as bad as the ancient rumors claim.

[Andrei Bobrov]

+1

[Jan]

@Zhuoyi Chen: Flags are thought to call admins or editors to care about contents, which conflict with the terms of use, e.g. if they are offending. You can use a comment to mention, that a solution is working.

@Andrei: Thanks. It is interesting, that your STRFIND solution gets faster, if the input contains less 1s, while the loops do not profit.

I think, although we have posted solutions of a homework, the overkill of 6 different methods has supported the OP to learn something new about Matlab. :-)

Answer 3

[Image Analyst]

Interested in the method I first thought of?

v =  [0,0,1,1,0,0,0,1,1,1] 
v2 = zeros(size(v)); % Initialize vector of same length.
props = regionprops(logical(v), 'Area', 'PixelIdxList');
for k = 1 : length(props)
  v2(props(k).PixelIdxList(1)) = props(k).Area;
end

[Andrei Bobrov]

+1

[Alexander Cranney]

bwconncomp may offer some speed improvements over regionprops. But I didn't know of either of these remarkable functions before seeing this, so thank you!