Smallest and Largest contiguous repeating sub-sequence in a sequence

Question

I am trying to solve a outdated quiz problem.
I am tasked to find the smallest and largest contiguous sequence of repeating numbers in a larger sequence.
e.g.

{1,3,6,17,19,3,6,5,4,2,5,6,17,19,3,6,7,5,78,100,101}

For the sequence above, the smallest (non-zero element sequence) and largest non extensible sub sequence would be smallest - 3,6 and largest - 6,17,19,3,6

Could not get started with an algorithm. Any help to get me started would be much appreciated.

Answer 1

To avoid having to enumerate every sequence, it is enough to observe that in any repeated subsequence the first two elements of each occurrence must be the same. In other words, every repeated pair could be the start of a longer repeated subsequence and every number that does not begin a repeated pair could not.

So in your example, the repeated pairs are 3,6 and 6,17. Each of these could start a longer sequence, and nothing else could.

So, start with a pass looking at each pair (N-1) and keep all of those that repeat. This will form a set of clusters of sequence starting points.

Then within each cluster take two sequences at a time and compare how far the match extends. Remember the shortest and longest. You have your answer.

In your example, first try to extend 3,6 for each occurrence. The maximum length is 2. Then try to extend 6,17. The maximum length is 5. Problem solved.

The data structure for recording the clusters is an interesting design point. I would probably use a dictionary keyed on the first two elements of the sequence and containing a list (or vector) of starting points (indexes into the original data).

This is an outline of an algorithm. It should be enough to provide a starting point if you already understand the problem and are a reasonably good programmer. I'm not sure I can provide much more help without actually writing the code.

Answer 2

You need a data structure and a way to manipulate it.

One possibility is a tree. Each node of the tree (except the root) contains a value equal to a number in the input sequence, but the same value may (in fact usually will) occur in multiple nodes of the tree. Each node also contains a list of "starting points", which could just be the relative positions of the elements of the list (0 through N-1). For any unidirectional path from the root to a node in the tree, the values stored in the nodes on the path are the numbers in a subsequence of the input sequence, and the starting points listed in the destination node are all the positions in the input sequence where a copy of that subsequence starts.

In your example, here are just a few of the nodes that would occur in the tree:

() -> (3, (1, 5, 14)) -> (6, (1, 5, 14)) -> (5, (5))

That is, () is the root node, one of its children is (3,(1,5,14)), and so forth. These nodes represent the fact that there is a one-element subsequence (3) starting at positions 1, 5, and 14; the subsequence (3,6) also starts at positions 1, 5, and 14; but the subsequence (3,6,5) occurs only at position 5. There are many other nodes I have not shown here, for example the ones representing the fact that a subsequence (3,6,17) starts at position 1, and that (3,6,7) starts at position 14.

To make this tree represent all subsequences starting at a given position in the input sequence, you start at that position and read consecutive numbers from the input until you reach the end of the input. As you read each number you move one step down the tree to a node containing that number (if there is no such node, you create it), and you append the given starting position in the list at that node.

The tree is complete when you have done this once for each possible starting position in the list. At that time, any repeated subsequence is represented by a node whose list contains two or more starting positions. The deepest such node tells you what the longest repeated subsequence was.

If the longest subsequence were all you needed, it would have been enough to keep a counter at each node instead of a list. But for the shortest non-extensible subsequence, it's helpful to know those starting positions. For example, choose any node you like in the tree. Consider the subsequence represented by that node. To determine that the subsequence can't be extended toward the end of the list, verify that none of the children of your chosen node has more than one starting point in its list. To determine that the subsequence can't be extended toward the start of the list, look at the numbers in the input sequence immediately before each of your chosen node's starting points, and verify that no two of those numbers are equal. You can do a breadth-first search of the tree and stop when you find a node that passes both of those tests.

But looking at the input again, I see that the subsequence (19,3,6) occurs twice, so perhaps I misunderstood your criteria for "shortest repeating subsequence". If what you mean is that there is at least one copy of (3,6), the one starting at position 1, that is repeated elsewhere in the input but cannot be extended forward or backward, then instead of "no two of those numbers are equal", the previous paragraph should say, "there is at least one number that occurs exactly once." That is, in the example, the subsequence (3,6) starting at position 1 is preceded by the value 1, and that is the only time that (3,6) is preceded by 1.

This is surely not the fastest way to get an answer, but it's better than some brute-force approaches might be. There are still plenty of implementation details to optimize. You might be able to optimize it much further; for example, rather than using the procedure I gave for filling in the nodes of the tree, perhaps you can use a procedure of the kind outlined by david.pfx, in which case the resulting tree will be much smaller (because you don't build a lot of nodes that have no purpose).

Answer 3

You could use patterns … To find the longest repeating subsequence try this …

{1, 3, 6, 17, 19, 3, 6, 5, 4, 2, 5, 6, 17, 19, 3, 6, 7, 5, 78, 100, 
  101} /. {___, Longest[y___], ___, Longest[y___], ___} :> y

This returns Sequence[6,17,19,3,6]

To find the shortest non-trivial (i.e., length 2 or greater) repeating subsequence try this …

{1, 3, 6, 17, 19, 3, 6, 5, 4, 2, 5, 6, 17, 19, 3, 6, 7, 5, 78, 100, 
  101} /. {___, Shortest[y___ /; Length[{y}] >= 2], ___, 
   Shortest[y___], ___} :> y

This returns Sequence[3,6]

Note: the answers are returned as Sequence objects. If, instead, you want *** lists *** returned change the final y that appears after the :> symbol to {y}.

I can express the same solution in more verbose terms as …

{1, 3, 6, 17, 19, 3, 6, 5, 4, 2, 5, 6, 17, 19, 3, 6, 7, 5, 78, 100, 
  101} /. {BlankNullSequence[], Longest[y___], BlankNullSequence[], 
   Longest[y___], BlankNullSequence[]} :> y

{1, 3, 6, 17, 19, 3, 6, 5, 4, 2, 5, 6, 17, 19, 3, 6, 7, 5, 78, 100, 
  101} /. {BlankNullSequence[], Shortest[y___ /; Length[{y}] >= 2], 
   BlankNullSequence[], Shortest[y___], BlankNullSequence[]} :> y