# Sequence matching problem is complicated, how can I break it down into easier smaller pieces?

I have two lists:

1:

``````1) A abc
2) A def
3) A ghi
4) B jkl
5) B mno
6) C fzy
7) C xxa
``````

2:

``````1) vsf
2) jkl
3) fzy
4) xxa
5) xyz
6) mno
7) def
8) abc
``````

I am trying to match each of the continuous sequences from list `1`--in this case there are two continuous sequences, A and B-- with its corresponding sequence in list `2`, with the following rules:

• The sequence in `2` can be discontinuous
• The sequence in `2` can run backwards or forwards
• If there is no complete match for `1` in `2`, the longest partial match should be returned

So the matches in my sample set, with list 1 matched to list 2, are:

``````Sequence A:
partial match
1 matches 8
2 matches 7

Sequence B:
discontinuous match
4 matches 2
5 matches 4

Sequence C:
continuous match
6 matches 3
7 matches 4
``````

The data sets are in Excel, so I'm planning to use either VBA or C#.

Can anyone help me break this problem down into simpler subtasks that need to get done, so that it will be simpler to write the application?

I know that normally it's best for me to show some code, but I'm having trouble even figuring out a pseudocode algorithm as a starting point in the design process.

EDIT:

After I wrote this, I realized that I'd forgotten to include a core part of the problem that made it more difficult: the lists contain non-unique values. For example, it might be that list 1 value 7 is `abc`, and list 2 value 4 is `abc`, with the same match result. So we need to match based on common subsequences rather than simply by doing a join based on individual values.

• am i right in thinking that you can just join the two lists and sort by the A,B,C column? – Ewan Dec 6 '17 at 10:46

So, if you join the two lists on the value you get:

``````1)  A   abc 8)  abc
1)  A   abc 9)  abc --example non unique match
2)  A   def 7)  def
3)  A   ghi
4)  B   jkl 2)  jkl
5)  B   mno 6)  mno
6)  C   fzy 3)  fzy
7)  C   xxa 4)  xxa
``````

If you now loop though this list, checking the forth column to check if it counts up or down rather than up AND down you should get your result.

It seems to me that you have a couple of ambiguous cases which complicate the counting loop. Otherwise you just need to check where the next match is at an ordinal greater or less than the last one and keep an 'up' and 'down' count.

• The sequence includes an out of order element. Should it be skipped the same as a non match, or does it end the match?

• A duplicate occurs in sequence, can it be skipped, or should the count start again from that point?

• If it counts up AND down he needs to find the longest contiguous run. – Sebastian Redl Dec 6 '17 at 14:45
• yes, although its not entirely clear what contiguous would mean in this context. could we skip an out of order match and continue? – Ewan Dec 6 '17 at 15:34
• I realized that a big part of the problem is that the lists contain non-unique values, which I admittedly didn't state in the original question. For example, it might be that list 1 value 7 is `abc`, and list 2 value 4 is `abc`. So we need to match based on common subsequences rather than simply by doing a join based on individual values. – sigil Dec 6 '17 at 16:11
• the join will work fine with non uniques, you can account for the duplicates when stepping through – Ewan Dec 6 '17 at 16:16
• Regarding "The sequence includes an out of order element..." the subsequences in list 2 can run in either direction, and a subsequence in list 1 can be fragmented among several subsequences in list 2. Regarding "A duplicate occurs in sequence...", many subsequences contain duplicates. A valid subsequence in list 1 might be `zyx,aab,aab,dec,fdf`, with non-contiguous matches in list 2 `zyx,aab,aab` and `fdf,dec`. – sigil Dec 6 '17 at 17:19