Thread Subject: Finding if a sequence occurs

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!

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

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

"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

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

"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

"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

"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

"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.

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

"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

"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
 

"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

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!!!!!

"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

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

"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

"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.

"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