This is a function to detect cycles in a back-trace. For example a cycle ('b', 'c', 'd') proceeded with 'a' could be:

>>> __cycles_detection(['a', 'b', 'c', 'd', 'b', 'c', 'd', 'b', 'c', 'd'])
(('b', 'c', 'd'),)

Args - funs (List[str]): functions list

Returns - list: the different cycles present in the back-trace

Can this algorithm be improved?

def __cycles_detection(funs):
    positions = {}
    for i in range(len(funs)):
        fun = funs[i]
        if fun in positions:
            positions[fun] = [i]

    lengths = {}
    for k, v in positions.items():
        if len(v) >= 2:
            l = v[1] - v[0]
            good = True
            for i in range(2, len(v)):
                if v[i] - v[i - 1] != l:
                    good = False
            if good:
                if l in lengths:
                    lengths[l].append((k, v))
                    lengths[l] = [(k, v)]

    cycles = []
    for k, v in lengths.items():
        l = sorted(v, key=lambda x: x[1][0])
        pat = []
        container = [l[0][0]]
        pos = l[0][1][0]
        for i in range(1, len(l)):
            _pos = l[i][1][0]
            if _pos == pos + 1:
                pos = _pos
                container = [l[i][0]]
                pos = _pos

        cycles += pat

    cycles = tuple(cycles)

    return cycles
  • 1
    \$\begingroup\$ Could you please post a simple usage example ? \$\endgroup\$ Sep 14, 2016 at 10:13
  • 2
    \$\begingroup\$ One of the reasons this is hard to review is that you don't clarify what things are doing and your variables/inline documentation do not help. \$\endgroup\$
    – enderland
    Sep 14, 2016 at 13:18
  • \$\begingroup\$ I agree with enderland here, do you have example use cases and their output to clarify what you're doing? \$\endgroup\$
    – Mast
    Sep 14, 2016 at 13:19
  • 5
    \$\begingroup\$ I expanded the very small example input you gave us, "This is a function to detect cycles in a back-trace [a,b,c,d,b,c,d,b,c,d...]". Feel free to edit my changes, and if you could add some more cycles it would be appreciated. Your word definition of this algorithm seems to want __cycles_detection([1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 1, 2, 1, 2]) to output ((1, 2, 3), (1, 2)) rather than ((3,),). \$\endgroup\$
    – Peilonrayz
    Sep 14, 2016 at 13:45

1 Answer 1


In fact, there isn't a single solution to find consecutive repetitions (cycles) in a sequence.

Here is an algorithm to find all repetition in a sequence.

def cycles_detection(funs):
    # Bigger cycle size first
    for size in reversed(range(2, 1 + len(funs) // 2)):
        # Find all consecutive sequences of size `size`
        for start in range(size):
            # Split the list by slices of size `size`, starting at position `start`
            end = size * ((len(funs) - start) // size) + start
            sequences = [tuple(funs[i:i + size]) for i in range(start, end, size)]
            sequences = filter(None, [tuple(funs[:start])] + sequences + [tuple(funs[end:])])

            # Init repetition to 1 then calculate consecutive repetitions
            groups = [(seq, 1) for seq in sequences]
            packing = [groups.pop(0)]
            while groups:
                prev_grp = packing[-1]
                next_grp = groups.pop(0)
                if prev_grp[0] == next_grp[0]:
                    packing[-1] = (prev_grp[0], prev_grp[1] + next_grp[1])

            # has cycle if any repetition is greater than 2
            has_cycle = any(grp[1] > 1 for grp in packing)
            if has_cycle:

With the following sequence, you'll have 3 possible solutions:

cycles_detection(['a', 'b', 'c', 'd', 'b', 'c', 'd', 'b', 'c', 'd', 'a'])

You'll get:

[(('a', 'b', 'c'), 1), (('d', 'b', 'c'), 2), (('d', 'a'), 1)]
[(('a',), 1), (('b', 'c', 'd'), 3), (('a',), 1)]
[(('a', 'b'), 1), (('c', 'd', 'b'), 2), (('c', 'd', 'a'), 1)]

Each list has tuple of the form (sequence, repetition), where:

  • sequence is a sub-sequence in funs (repeated or not),
  • repetition is the number of occurence of consecutive sequences.

The question is: How to find the best result? Is it the longest repeated sequence, or the most repeated sequence?


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.