Best strategy for finding a pattern in a sequence of integers

[Banibrata Dutta]

Haven't followed the entire thread, so I could be making a silly,
out-of-place remark, and apologies in advance for the same.However, to me it
looks like Slaunger wants to find 2 of the longest repeating patterns, and
not just 2 specific patterns (though from the introductory test, it appears
to be on the contrary. If so, i.e. looking for longest repeating patters,
this is largely a problem of choosing the right algorithm, and not so much
Python. Something like KMP (Knuth Morris Pratt) algo may help.

On Fri, Nov 21, 2008 at 10:40 PM, Gerard flanagan <grflanagan at gmail.com>wrote:

> Slaunger wrote:
>
>> Hi all,
>>
>> I am a Python novice, and I have run into a problem in a project I am
>> working on, which boils down to identifying the patterns in a sequence
>> of integers, for example
>>
>> .... 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 9 3 3 0 3 3 0 3 3 0 3 3 0 10 6 6
>> 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 9 3 3 0 3 3 0 3 3 0 3 3 0 10 6 6
>> 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 9 3 3 0 3 3 0 3 3 0 3 3 0 10 6 6
>> 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 9 3 3 0 3 3 0 3 3 0 3 3 0 10 6 6
>> 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 ...
>>
>> I want to process this such that I get out two patterns, like:
>> (9, 3, 3, 0, 3, 3, 0, 3, 3, 0, 3, 3, 0)
>> and
>> (10, 6, 6, 1, 6, 6, 1, 6, 6, 1, 6, 6, 1, 6, 6, 1, 6, 6, 1, 6, 6, 1)
>>
>>
> Maybe:
>
> #-----------------------------------------------------------------
> data = '''
> 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 9 3 3 0 3 3 0 3 3 0 3 3 0 10 6 6
> 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 9 3 3 0 3 3 0 3 3 0 3 3 0 10 6 6
> 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 9 3 3 0 3 3 0 3 3 0 3 3 0 10 6 6
> 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 9 3 3 0 3 3 0 3 3 0 3 3 0 10 6 6
> 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1 6 6 1'''
>
> data = [int(x) for x in data.split()]
>
> from itertools import groupby
>
> S1 = [0, 3, 9]
>
> s = set()
> for k, g in groupby(data, lambda x: x in S1):
>    seq = tuple(g)
>    # maybe the next line should be 'if 9 in seq or 10 in seq'?
>    if seq[0] in [9, 10]:
>        s.add(seq)
>
> print s
> #------------------------------------------------------------------
> set(
> [(9, 3, 3, 0, 3, 3, 0, 3, 3, 0, 3, 3, 0),
> (10, 6, 6, 1, 6, 6, 1, 6, 6, 1, 6, 6, 1, 6, 6, 1, 6, 6, 1, 6, 6, 1)])
>
> hth
>
> G.
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>



-- 
regards,
Banibrata
http://www.linkedin.com/in/bdutta
http://octapod.wordpress.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20081121/c22d0126/attachment-0001.html>