5
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Could you please post a simple usage example ? \$\endgroup\$ – яүυк Sep 14 '16 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 '16 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 '16 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 '16 at 13:45
1
\$\begingroup\$

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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