4

I have an array of random numbers lets say:

[10,11,12,14,15,16,17,18,19,20, 11, 12, 14,25,25,26,27,28,29]

I have to detect repeated sequences (witch are in fact errors)

with length bigger then a specific number (2).

Is there any good algorithm for this ?

what I have for now:

int minLenght = 3;
int[] data = {1,2,3};

for(int i = 0; i < data.length; i++){
    for(int j = 0; j < data.length; j++){
        if ( data[i] == data[j]){
            int l = 0;
            int ii = i;
            int jj = j;
            while(data[ii] == data[jj]){
                ii++;
                jj++;
                l++;
            }
            if(l >= minLenght){
                print('['+i+'-'+ii+'] same as ['+j+'-'+jj+']');
            }
        }
    }
}
2
  • 1
    what are restrictions on memory usage and execution time? what is expected length of a sequence? Nov 27, 2012 at 22:13
  • no memory restrictions, the set is usually 20-200 items and repeated sequences are rare (errors).The checked length is 5(but may change).
    – d.raev
    Nov 28, 2012 at 5:33

3 Answers 3

4

One way is to store sequences of length L (one bigger than your specific length) in a hash table.

If you ever find a sequence is already in the hash table, then you have found a repeat of length >= L.

e.g. Python code

A=[10,11,12,14,15,16,17,18,19,20,11,12,14,25,25,26,27,28,29]
S=set()
L=2+1
for i in xrange(len(A)-L+1):
    key=tuple(A[i:i+L])
    if key in S:
        print i
    else:
        S.add(key)

This prints out the locations of repeated sequences with length greater than 2.

2
  • thanks for the idea (I start to like python). But L should "minimum length" and there is no reference to the first sequence.
    – d.raev
    Nov 28, 2012 at 6:11
  • You can modify this method slightly to get the index of the first sequence too. Change S=set() to S=dict(); change S.add(key) to S[key] = i; and change print i to print S[key].
    – Kevin
    Nov 28, 2012 at 12:51
0

You could use regexps, except the list format shown is irregular. I use Python below and 'regularise' the list format turning it into a string before applying a regular expression looking for duplicated sequences of numbers/non-numbers:

>>> import re
>>> numbers = [10,11,12,14,15,16,17,18,19,20, 11, 12, 14,25,25,26,27,28,29]
>>> sep = ', '
>>> txt = sep + sep.join(str(x) for x in numbers) + sep
>>> txt
', 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 11, 12, 14, 25, 25, 26, 27, 28, 29, '
>>> re.search(r'\D((?:\d+\D+){2,}).*\1', txt).groups()
('11, 12, 14, ',)

I normally try and minimize my use of regexps but this does detect the duplication.

0

I don't know if there is a special algorithm for this, but my proposal would be this:

loop1 over array[i]:
  loop2 over array[j] starting with i+1:
    dist=array[j]-array[i];
    if dist==specific_number:
      array_result.append(array[i] +""+""+array[j]) 

This would be my simple logic.

Your Answer

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

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