1

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.

3
  • 2
    Is the quiz really formulated in terms of repeating sets? I would rather say repeated (sub)sequences since a set does not define any sequence for its elements.
    – Giorgio
    Mar 30, 2014 at 15:05
  • 1
    Also, you should say that you only consider repeated sub-sequences that are maximal in the sense that they cannot be extended. Otherwise the smallest sub-sequence would always trivially be the empty sub-sequence.
    – Giorgio
    Mar 30, 2014 at 15:08
  • @Giorgio, I was more focused on the algorithm, sorry I picked a wrong mathematical term set. I agree with you I actually mean sequences and sub sequences. Mar 31, 2014 at 6:58

3 Answers 3

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.

3
  • I could not understand when you say - "it is enough to observe that in any repeated subsequence the first two elements of the pair must be the same". Please help me understand it. Apr 2, 2014 at 9:57
  • @david.pfx: In the OP's example, the repeated pairs are 3,6, 6,17, 17,19, and 19,3. Your answer does not make it clear how/why you are ignoring 17,19 and 19,3.
    – Brian
    May 13, 2015 at 18:39
  • It's fairly obvious that the ones I omitted share a common predecessor, which means they cannot be the start of a longest sequence. It's not that obvious how to incorporate that into the algorithm. Fortunately I don't think you have to. Your point is valid, but the algorithm works without considering it.
    – david.pfx
    May 15, 2015 at 10:11
0

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

2
  • when you say - "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)" what does starting points signify? In the example I used would starting points mean 1,2 (assuming a 0-based index for the sequence) for the shortest sequence - {3,6}? Apr 2, 2014 at 10:09
  • I edited the answer to try to clarify the data structure, and to further discuss the meaning of "shortest repeating subsequence".
    – David K
    Apr 2, 2014 at 11:35
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.