connected components of vector?
Misha Koshelev
I have a vector, say
a = [ 1 2 3 8 9 ];
I would like a command that will give me the vectors [ 1 2 3 ] and [ 8 9 ] in some form. Is there a command like this, especially a vectorized one? I am vectorizing a function and it seems like if I have to iterate through anyway and find the connected components I don't think my vectorization will help much... am I wrong?
Thank you
Misha
John D'Errico
It seems to me that finding an algorithm for anything
requires that you define what your goal is, defining
the specific problem. So before you start, tell us
what is the characteristic of a connected component?
Does it have something to do with the difference
between successive elements? If so, compute that
difference and think about what characteristic the
difference must have for elements that are "connected".
John
Nasser Abbasi
> Hi,
>
> I have a vector, say
>
> a = [ 1 2 3 8 9 ];
>
> I would like a command that will give me the vectors [ 1 2 3 ] and [ 8 9 ]
> in some form.
a = [ 1 2 3 8 9 ];
K>> a = [ 1 2 3 8 9 ];
K>> a(1:3)
1 2 3
K>> a(4:end)
8 9
" Is there a command like this, especially a vectorized one? I am
vectorizing a function and it seems like if I have to iterate through anyway
and find the connected components I don't think my vectorization will help
much... am I wrong?
>
> Thank you
> Misha
You are welcome
--Nasser
Misha Koshelev
Perhaps I was not clear. I have an arbitrary vector a. I want to find all the _largest_ vectors such that each element
[ x_1 x_2 x_3 ... x_n ]
is such that x_i = x_{i-1}
In other words, for an arbitrary vector, i would like a command that returns _all_ the vectors that are part of the original vector that match this criterion.
So, for example, for [1 2 3 8 9 10 22 23 24]
the command should return the vectors:
[1 2 3], [8 9 10], [22 23 24].
Alternately, how can I code this so it is either (a) vectorized or (b) JIT-able?
Thank you
Misha
John D'Errico
Sigh. OBVIOUSLY I was not clear either.
What characteristic of these SUBvectors are
you looking for? It is clearly NOT
x_i == x_{i-1}
as you state, as that never happens in the
examples you give. It APPEARS to be
x(i) == (x(i-1) + 1)
Is this the distinguishing characteristic of a
"vector", as you chose to define it?
If that is the case, what happens when you
apply diff to x?
What characteristic will you see for consecutive
elements of such a sequence that differ by
exactly 1? Can you find them?
Break your problem into smaller subproblems
that you can solve. In case I was still being
insufficiently blunt here, what does this do?
find(diff(x)~=1)
Can you use this?
Again. Break a difficult problem into simpler,
smaller subproblems that you can solve. When
you have a problem that you are unable to solve,
carefully (and correctly) define your goal in the
problem. That definition will often contain the
solution to your problem.
John
Bruno Luong
a = [ 1 2 3 8 9 ]; % call unique if necessary to put a in such form
b=a-(1:length(a));
b = [true; diff(b(:))~=0; true];
split = mat2cell(a(:).',1,diff(find(b)));
split{:}
% Bruno
Misha Koshelev
Thank you. Very helpful. A bit cryptic but very very helpful.
Misha
Matt Fig
>
> Misha
Vectorized code often is cryptic! Bruno's code is actually not that bad (as far as being cryptic) compared to some snippets I have seen.
Misha Koshelev
Thanks again for the code.
I am iterating over the split cell array as follows:
for idx=1:numel(split)
ks=split{idx};
ks=union(ks,ks+1);
...
end
I am guessing the union here (and growing ks vector) will ruin vectorization. Idea is I need to add last element here, but I can't add it to my original vector as that will mess up how it is split and I don't know how to add it to the cell array (union doesn't seem to work). Any advice?
Thanks
Misha