# Cycle detection

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].append(i)
else:
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
break
if good:
if l in lengths:
lengths[l].append((k, v))
else:
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:
container.append(l[i][0])
pos = _pos
else:
pat.append(tuple(container))
container = [l[i][0]]
pos = _pos

pat.append(tuple(container))
cycles += pat

cycles = tuple(cycles)

return cycles

• Could you please post a simple usage example ? – яүυк Sep 14 '16 at 10:13
• 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. – enderland Sep 14 '16 at 13:18
• I agree with enderland here, do you have example use cases and their output to clarify what you're doing? – Mast Sep 14 '16 at 13:19
• 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,),). – Peilonrayz Sep 14 '16 at 13:45

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])
else:
packing.append(next_grp)

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


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?