3

Suppose I have a sequence:

    Seq = 'hello my name'

and a string:

    Str = 'hello hello my friend, my awesome name is John, oh my god!'

And then I look for matches for my sequence within the string, so I get the "word" index of each match for each word of the sequence in a cell array, so the first element is a cell containing the matches for 'hello', the second element contains the matches for 'my' and the third for 'name'.

    Match = {[1 2];      %'hello' matches
             [3 5 11];   %'my' matches
             [7]}        %'name' matches

I need code to somehow get an answer saying that possible sub-sequence matches are: 

    Answer = [1 3 7;     %[hello my name]
              1 5 7;     %[hello my name]
              2 3 7;     %[hello my name]
              2 5 7;]    %[hello my name]

In such a way that "Answer" contains all possible ordered sequences (that's why my(word 11) never appears in "Answer", there would have to be a "name" match after position 11.

NOTE: The length and number of matches of "Seq" may vary.

Luis Mendo
  • 110,752
  • 13
  • 76
  • 147
ACenTe25
  • 75
  • 5

1 Answers1

4

Since the length of Matches may vary, you need to use comma-separated lists, together with ndgrid to generate all combinations (the approach is similar to that used in this other answer). Then filter out combinations where the indices are not increasing, using diff and logical indexing:

cc = cell(1,numel(Match)); %// pre-shape to be used for ndgrid output
[cc{end:-1:1}] = ndgrid(Match{end:-1:1}); %// output is a comma-separated list
cc = cellfun(@(v) v(:), cc, 'uni', 0) %// linearize each cell
combs = [cc{:}]; %// concatenate into a matrix
ind = all(diff(combs.')>0); %'// index of wanted combinations
combs = combs(ind,:); %// remove unwanted combinations

The desired result is in the variable combs. In your example,

combs =
     1     3     7
     1     5     7
     2     3     7
     2     5     7
Community
  • 1
  • 1
Luis Mendo
  • 110,752
  • 13
  • 76
  • 147
  • Thanks a lot, it works perfectly! I didn't know the ndgrid and cellfun functions, still have to understand exactly how it works because those 2 steps aren't clear to me, but I'll investigate that on my own. Thank you, sir! – ACenTe25 Feb 18 '14 at 23:49
  • @ACenTe25 Feel free to ask if you need after you investigate :-) – Luis Mendo Feb 19 '14 at 00:02
  • I think I understand now. I could get a similar result even if I wrote `[cc{1:end}] = ndgrid(Match{1:end});` right? The only change would be the order in which combinations are delivered in `combs`, if I understand correctly. – ACenTe25 Feb 19 '14 at 17:05
  • @ACenTe25 Exactly. The only purpose of that is to get the same order as in your question. And of course you could abbreviate `[cc{1:end}] = ndgrid(Match{1:end});` to `[cc{:}] = ndgrid(Match{:});` – Luis Mendo Feb 19 '14 at 17:20