Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Finding if a sequence occurs

Subject: Finding if a sequence occurs

From: Diego Zegarra

Date: 18 Feb, 2009 03:05:05

Message: 1 of 19

I know this would work,
a=[2 4 5 3 1 6];
findstr(a,[2 4])
ans =1
findstr(a,[1 6])
ans =5

Now what if,

a=[2 4 5 ;3 1 6]; (2x3 matrix)

What I am trying to do is find how many times each sequence occurs. Let me explain what I mean by this, assume this numbers 1 through 6 each represent one job. So let's say that the sequence in which they run is now job 2 first, then job 4, then 5 and so on.

Now I want to see how many times is job 2 after job 1, job 3 after job 1, job 4 after job 1,..., job 1 after job 2, job 3 after job 2..... Every possible sequence of jobs. So I want to create a matrix (lets call it "d") where I have 6 rows and 6 columns and I can put a 1 if the sequence is present or a 0 if it is not. So in this case d(2,4) = 1, d(4,5)=1 and so on...


Thanks!

Subject: Finding if a sequence occurs

From: Matt Fig

Date: 18 Feb, 2009 05:01:01

Message: 2 of 19

I assume the size of a is merely a nuisance, that is there is no special meaning to having a sequence occur in the second row versus the first.

a=[2 4 5 ;3 1 6];
na = numel(a);
a(:,end+1) = NaN;
at = a.';
arow = at(:)';
b = npermutek(1:na,2); % on the FEX
vct = 1:(na+1):na^2;
b(vct,:) = [];

d = zeros(na);
for ii = 1:(na^2 - length(vct))
    t1 = findstr(arow,b(ii,:));
    if ~isempty(t1)
        d(b(ii,1),b(ii,2)) = length(t1);
    end
end
d




RLScIE=MSSEEF)cEIE$}QPFSSZEjIqc1]XLLYYSXIjcMRKccGTTOcXcEGQP

Subject: Finding if a sequence occurs

From: Matt Fig

Date: 18 Feb, 2009 05:35:02

Message: 3 of 19

Even simpler (if I am on the right track to what you want)


a=[2 4 5 ;2,5,6];
a(:,end+1) = NaN;
at = a.';
arow = at(:)';
d = zeros(6);

for ii = 1:(numel(arow)-1)
    if ~isnan([arow(ii),arow(ii+1)])
        d(arow(ii),arow(ii+1)) = d(arow(ii),arow(ii+1)) + 1;
    end
end
d





wqmeY`gglwdae]c`]gfhY&~l][lw2Y_nwgYa]gwYE8Q`wZfgYw=YZwmh~[d

Subject: Finding if a sequence occurs

From: Bruno Luong

Date: 18 Feb, 2009 07:29:03

Message: 4 of 19

"Matt Fig" <spamanon@yahoo.com> wrote in message <gng6m6$hlf$1@fred.mathworks.com>...
> Even simpler (if I am on the right track to what you want)
>
>
> a=[2 4 5 ;2,5,6];
> a(:,end+1) = NaN;
> at = a.';
> arow = at(:)';
> d = zeros(6);
>
> for ii = 1:(numel(arow)-1)
> if ~isnan([arow(ii),arow(ii+1)])
> d(arow(ii),arow(ii+1)) = d(arow(ii),arow(ii+1)) + 1;
> end
> end
> d
>

I know Matt does not like accumarray, but it is so convenient...

a=[2 4 5 ;2,5,6];
a(:,end+1) = NaN;
at = a.';
arow = at(:)';

seq=[arow(1:end-1); arow(2:end)];
seq(:,any(isnan(seq)))=[];
d = accumarray(seq.',ones(size(seq,2),1),[6 6])

% Bruno

Subject: Finding if a sequence occurs

From: Bruno Luong

Date: 18 Feb, 2009 07:36:02

Message: 5 of 19

Even simpler:

a=[2 4 5 ;2,5,6];

% Engine
seq=reshape(cat(3,a(:,1:end-1),a(:,2:end)),[],2);
d = accumarray(seq,ones(size(seq,1),1),[6 6])
 
% Bruno

Subject: Finding if a sequence occurs

From: Jos

Date: 18 Feb, 2009 07:59:02

Message: 6 of 19

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gngdp2$226$1@fred.mathworks.com>...
> Even simpler:
>
> a=[2 4 5 ;2,5,6];
>
> % Engine
> seq=reshape(cat(3,a(:,1:end-1),a(:,2:end)),[],2);
> d = accumarray(seq,ones(size(seq,1),1),[6 6])
>
> % Bruno

or use simple indexing:

a=[2 4 5 ;2,5,6];

d = zeros(max(a(:))) ;
d(sub2ind(size(d2), a(:,1:end-1), a(:,2:end))) = 1

Jos

Subject: Finding if a sequence occurs

From: Bruno Luong

Date: 18 Feb, 2009 08:07:02

Message: 7 of 19

"Jos " <#10584@fileexchange.com> wrote in message <gngf46$10v$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gngdp2$226$1@fred.mathworks.com>...

>
> or use simple indexing:
>
> a=[2 4 5 ;2,5,6];
>
> d = zeros(max(a(:))) ;
> d(sub2ind(size(d2), a(:,1:end-1), a(:,2:end))) = 1
>

What if a sequence repeats more than one?

Bruno

Subject: Finding if a sequence occurs

From: Jos

Date: 18 Feb, 2009 08:22:01

Message: 8 of 19

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gngfj6$c14$1@fred.mathworks.com>...
> "Jos " <#10584@fileexchange.com> wrote in message <gngf46$10v$1@fred.mathworks.com>...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gngdp2$226$1@fred.mathworks.com>...
>
> >
> > or use simple indexing:
> >
> > a=[2 4 5 ;2,5,6];
> >
> > d = zeros(max(a(:))) ;
> > d(sub2ind(size(d2), a(:,1:end-1), a(:,2:end))) = 1
> >
>
> What if a sequence repeats more than one?
>
> Bruno

Hi Bruno, note that that is a different problem! The OP wrote: "So I want to create a matrix (lets call it "d") where I have 6 rows and 6 columns and I can put a 1 if the sequence is present or a 0 if it is not."

If the numbers of sequence are to be counted, ACCUMARRAY or SPARSE can be used.

Jos

Subject: Finding if a sequence occurs

From: Steve Amphlett

Date: 18 Feb, 2009 09:52:02

Message: 9 of 19

"Diego Zegarra" <diegozbb@gmail.com> wrote in message <gnftt0$1jh$1@fred.mathworks.com>...
> I know this would work,
> a=[2 4 5 3 1 6];
> findstr(a,[2 4])
> ans =1
> findstr(a,[1 6])
> ans =5
>
> Now what if,
>
> a=[2 4 5 ;3 1 6]; (2x3 matrix)
>
> What I am trying to do is find how many times each sequence occurs. Let me explain what I mean by this, assume this numbers 1 through 6 each represent one job. So let's say that the sequence in which they run is now job 2 first, then job 4, then 5 and so on.
>
> Now I want to see how many times is job 2 after job 1, job 3 after job 1, job 4 after job 1,..., job 1 after job 2, job 3 after job 2..... Every possible sequence of jobs. So I want to create a matrix (lets call it "d") where I have 6 rows and 6 columns and I can put a 1 if the sequence is present or a 0 if it is not. So in this case d(2,4) = 1, d(4,5)=1 and so on...

(Plenty of answers already provided, I'd use sparse)

This question an various permutations of it is cropping up a lot recently. What's the context? Just interested.

Subject: Finding if a sequence occurs

From: Bruno Luong

Date: 18 Feb, 2009 10:06:01

Message: 10 of 19

Of course, accumarray AND sparse can be together

a=[2 4 5 6 ; 2 5 6 2];
seq=reshape(cat(3,a(:,1:end-1),a(:,2:end)),[],2);
d = accumarray(seq,ones(size(seq,1),1),[6 6], [], 0, true) % last flag is for sparse

% Bruno

Subject: Finding if a sequence occurs

From: Jos

Date: 18 Feb, 2009 10:50:02

Message: 11 of 19

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gngmi9$692$1@fred.mathworks.com>...
> Of course, accumarray AND sparse can be together
>
> a=[2 4 5 6 ; 2 5 6 2];
> seq=reshape(cat(3,a(:,1:end-1),a(:,2:end)),[],2);
> d = accumarray(seq,ones(size(seq,1),1),[6 6], [], 0, true) % last flag is for sparse
>
> % Bruno

In this case I would recommend the direct use of SPARSE:

a=[2 4 5 6 ; 2 5 6 2];
d = sparse(a(:,1:end-1),a(:,2:end),1,[6 6])

Jos

Subject: Finding if a sequence occurs

From: Bruno Luong

Date: 18 Feb, 2009 11:54:01

Message: 12 of 19

"Jos " <#10584@fileexchange.com> wrote in message <gngp4q$og0$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gngmi9$692$1@fred.mathworks.com>...
> > Of course, accumarray AND sparse can be together
> >
> > a=[2 4 5 6 ; 2 5 6 2];
> > seq=reshape(cat(3,a(:,1:end-1),a(:,2:end)),[],2);
> > d = accumarray(seq,ones(size(seq,1),1),[6 6], [], 0, true) % last flag is for sparse
> >
> > % Bruno
>
> In this case I would recommend the direct use of SPARSE:
>
> a=[2 4 5 6 ; 2 5 6 2];
> d = sparse(a(:,1:end-1),a(:,2:end),1,[6 6])
>
> Jos

Right Jos. I always forgot sparse accumulates values for the same indice-pair.

Bruno
 

Subject: Finding if a sequence occurs

From: Jos

Date: 18 Feb, 2009 13:11:01

Message: 13 of 19

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
...
> Right Jos. I always forgot sparse accumulates values for the same indice-pair.

Having worked with ancient versions of ML occasionally has its advantages. And also its disadvantages, as I usually tend to ignore the flexibility of accumarray ...

Jos

Subject: Finding if a sequence occurs

From: Diego Zegarra

Date: 18 Feb, 2009 16:08:01

Message: 14 of 19

Hi Jos,
I've never used sparse and have tried to read about it and look examples but I am quite not getting it and the following two lines provided give an error.
> a=[2 4 5 6 ; 2 5 6 2];
> d = sparse(a(:,1:end-1),a(:,2:end),1,[6 6])

??? Error using ==> sparse
Not enough input arguments.

I was wondering if you could help me out to see what was the problem. Or should I just use simple indexing as shown,

a=[2 4 5 ;3,1,6];

d = zeros(max(a(:))) ;
d(sub2ind(size(d2), a(:,1:end-1), a(:,2:end))) = 1

This operation is done multiple times throughout the code so the fastest way would be the best. I do not if I stated this before or not but a sequence can only occur once. Each number represents a job, where it can only be assigned once. So in a you will only see one 1, one 2, one 3..... For whoever asked what was it that I am doing, I am designing a metaheuristic for an unrelated parallel machine scheduling problem.


Thanks!!!!!

Subject: Finding if a sequence occurs

From: Bruno Luong

Date: 18 Feb, 2009 16:18:02

Message: 15 of 19

"Diego Zegarra" <diegozbb@gmail.com> wrote in message <gnhbp1$2oe$1@fred.mathworks.com>...
> Hi Jos,
> I've never used sparse and have tried to read about it and look examples but I am quite not getting it and the following two lines provided give an error.
> > a=[2 4 5 6 ; 2 5 6 2];
> > d = sparse(a(:,1:end-1),a(:,2:end),1,[6 6])
>
> ??? Error using ==> sparse
> Not enough input arguments.
>
> I was wondering if you could help me out to see what was the problem. Or should I just use simple indexing as shown,

Typo it should be:
d = sparse(a(:,1:end-1),a(:,2:end),1,6,6)

Bruno

Subject: Finding if a sequence occurs

From: Diego Zegarra

Date: 18 Feb, 2009 16:47:01

Message: 16 of 19

Bruno,

That does not create the matrix though, its the same as not putting the sixes in, look

>> a=[2 4 5 6 ; 2 5 6 2];
d = sparse(a(:,1:end-1),a(:,2:end),1,6,6)
d =
   (6,2) 1
   (2,4) 1
   (2,5) 1
   (4,5) 1
   (5,6) 2
>> d = sparse(a(:,1:end-1),a(:,2:end),1)
d =
   (6,2) 1
   (2,4) 1
   (2,5) 1
   (4,5) 1
   (5,6) 2

Subject: Finding if a sequence occurs

From: Bruno Luong

Date: 18 Feb, 2009 18:04:02

Message: 17 of 19

"Diego Zegarra" <diegozbb@gmail.com> wrote in message <gnhe25$bln$1@fred.mathworks.com>...
> Bruno,
>
> That does not create the matrix though, its the same as not putting the sixes in, look
>
> >> a=[2 4 5 6 ; 2 5 6 2];
> d = sparse(a(:,1:end-1),a(:,2:end),1,6,6)
> d =
> (6,2) 1
> (2,4) 1
> (2,5) 1
> (4,5) 1
> (5,6) 2
> >> d = sparse(a(:,1:end-1),a(:,2:end),1)
> d =
> (6,2) 1
> (2,4) 1
> (2,5) 1
> (4,5) 1
> (5,6) 2

It is *SPARSE* matrix, but it's still a matrix of the size 6x6. You can inquires any element by typing
> d(i,j).

If you prefer, you can transform it to full matrix
> D = full(d)

% Bruno

Subject: Finding if a sequence occurs

From: Steve Amphlett

Date: 18 Feb, 2009 18:25:03

Message: 18 of 19

"Diego Zegarra" <diegozbb@gmail.com> wrote in message <gnhbp1$2oe$1@fred.mathworks.com>...
> Hi Jos,
> I've never used sparse and have tried to read about it and look examples but I am quite not getting it and the following two lines provided give an error.
> > a=[2 4 5 6 ; 2 5 6 2];
> > d = sparse(a(:,1:end-1),a(:,2:end),1,[6 6])
>
> ??? Error using ==> sparse
> Not enough input arguments.
>
> I was wondering if you could help me out to see what was the problem. Or should I just use simple indexing as shown,
>
> a=[2 4 5 ;3,1,6];
>
> d = zeros(max(a(:))) ;
> d(sub2ind(size(d2), a(:,1:end-1), a(:,2:end))) = 1
>
> This operation is done multiple times throughout the code so the fastest way would be the best. I do not if I stated this before or not but a sequence can only occur once. Each number represents a job, where it can only be assigned once. So in a you will only see one 1, one 2, one 3..... For whoever asked what was it that I am doing, I am designing a metaheuristic for an unrelated parallel machine scheduling problem.



sparse() is neat because it allows you to avoid all that ind2sub/sub2ind malarkey to assign values to an arbitrary set of (i,j) locations. Plus there's the adding up feature, which isn't obvious but is very useful in some situations.

So we end up with the odd situation of using sparse() because it's more useful & flexible, even if you don't want or need sparse matrices.

Subject: Finding if a sequence occurs

From: Steven Lord

Date: 18 Feb, 2009 18:28:58

Message: 19 of 19


"Steve Amphlett" <Firstname.Lastname@Where-I-Work.com> wrote in message
news:gnhjpv$sc5$1@fred.mathworks.com...

*snip*

> sparse() is neat because it allows you to avoid all that ind2sub/sub2ind
> malarkey to assign values to an arbitrary set of (i,j) locations. Plus
> there's the adding up feature, which isn't obvious but is very useful in
> some situations.
>
> So we end up with the odd situation of using sparse() because it's more
> useful & flexible, even if you don't want or need sparse matrices.

If you like the accumulation behavior, but don't need or want a sparse
matrix, use ACCUMARRAY.

--
Steve Lord
slord@mathworks.com

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us