On Thu, 21 Apr 2016 06:53 pm, Oscar Benjamin wrote: > On 21 April 2016 at 04:07, Steven D'Aprano <st...@pearwood.info> wrote: >> I want to group repeated items in a sequence. For example, I can group >> repeated sequences of a single item at a time using groupby: >> >> >> from itertools import groupby >> for key, group in groupby("AAAABBCDDEEEFFFF"): >> group = list(group) >> print(key, "count =", len(group)) >> >> >> outputs: >> >> A count = 4 >> B count = 2 >> C count = 1 >> D count = 2 >> E count = 3 >> F count = 4 >> >> >> Now I want to group subsequences. For example, I have: >> >> "ABCABCABCDEABCDEFABCABCABCB" >> >> and I want to group it into repeating subsequences. I can see two ways to >> group it: >> >> ABC ABC ABCDE ABCDE F ABC ABC ABC B > > There are some algorithms (helpfully shown in Python) here: > > https://en.wikipedia.org/wiki/Cycle_detection
It's not necessarily a cycle though. Consider a sequence of function calls: def f(x): return g(x) def g(x): if x < 7: return h(x) elif x < 50: return g(x//2) else: return x+f(x-1) def h(x): raise ValueError # oops, a bug and a function call f(54). That will result in the chain of calls: f(54) -> g(54) -> f(53) -> g(53) -> f(52) -> g(52) -> f(51) -> g(51) -> f(50) -> g(50) -> g(25) -> g(12) -> g(6) -> h(6) raises So you have that almost-cycle f calls g calls f, but it isn't periodic because you break out of it. I'd still like to detect the repeated f->g calls. -- Steven -- https://mail.python.org/mailman/listinfo/python-list