How to determine cycles in a list?

Question

Consider a list of integer indices, indices. All elements of indices are within the bounds of the list indices. All the values in the list indices are unique. Example [2, 0, 1, 4, 3, 5].

Given an index, (e.g 0), move on to indices[0] (i.e 2 in the example above). Repeating that can be done indefinitely. A cycle occurs when a move returns to an already visited index. There is always at least one cycle. The sum of the lengths of the cycles is equal to the length of the list indices.

I need to create a function cycles(indices) that returns a list of all cycles in indices.

For the example above, the expected output list is [[2, 0, 1], [4, 3], [5]].

For the list [0, 1, 2, 3], the cycles are trivial and of the form [[0], [1], [2], [3]].

Note: The order of the output cycles and the order of the indices do not matter. For example: [[2, 0, 1], [4, 3], [5]] is equivalent to [[3, 4], [0, 1, 2], [5]]

This is the code I have come up with thus far:

def cycles(indices):
    cycles = []
    old_i = []
    i = 0
    while i in range(len(indices)):
        old_i.append(i)
        i = indices[i]
        if i in old_i:
            cycles.append(old_i)
            i = max(old_i) + 1
            old_i = []

    return cycles

The problem with my code is that it does not recheck if there is a smaller cycle within the elements of a bigger cycle, if it has already passed the elements of the smaller cycle. Any suggestions as to how to solve this coding problem?

Please note, I am just beginning to learn how to program and I am taking an introductory online course, so I would appreciate simple solutions.

Answer 1

It looks like a perfect problem for graph theory. You can connect elements from the list to their indices and look for connected components in the resulting graph. networkx is the most popular Python package for network analysis:

import networkx as nx

lst = [2, 0, 1, 4, 3, 5]

G = nx.Graph()
G.add_edges_from(enumerate(lst))
print(list(nx.connected_components(G)))
# [{0, 1, 2}, {3, 4}, {5}]

Answer 2

you can try this.

def cycles(indices):

    sub =[]
    i=0
    result = []
    remaining = indices[:]

    while remaining:
        i = indices[i]
        if(i in sub):
            remaining = [ a for a in remaining if a not in sub]
            result.append(sub)
            sub = []
            if remaining:
                i=remaining[0]

        sub.append(i)
    return result

r = cycles([2, 0, 1, 4, 3, 5])
print(r)
#[[2, 1, 0], [4, 3], [5]]

r = cycles([0,1,2,3,4,5])
print(r)
#[[0], [1], [2], [3], [4], [5]]

Answer 3

One crude solution, using sets to track which indices we've visited already:

def cycles(indices):

    def get_loop(indices, idx):             # this funtion returns a loop, starting from index `idx`
        seen, loop = set(), []
        while True:
            v = indices[idx]                # get index on position `idx`
            if v not in seen:               # have we seen index `v` already?
                loop.append(idx)            # no, add it as part of the loop
                seen.add(v)                 #   update set `seen` with index `v`
                idx = v                     #   set current index `idx` with index `v`
            else:
                break                       # yes, that means we closed the loop
        return loop                         # return this loop

    rv, seen = [], set()
    for i in indices:                       # iterate over all indices
        if i not in seen:                   # is index `i` part of any loop we already have?
            loop = get_loop(indices, i)     # no, so call get_loop() with starting index `i`
            rv.append(loop)                 # we add this loop to the result list
            seen.update(loop)               # update set `seen` with all indices inside this loop

    return rv

print(cycles([2, 0, 1, 4, 3, 5]))
print(cycles([0, 1, 2, 3, 4, 5]))
print(cycles([12, 0, 8, 10, 9, 6, 5, 4, 13, 7, 17,14, 2,18, 16, 1, 11, 19, 3, 15]))

Prints:

[[2, 1, 0], [4, 3], [5]]
[[0], [1], [2], [3], [4], [5]]
[[12, 2, 8, 13, 18, 3, 10, 17, 19, 15, 1, 0], [9, 7, 4], [6, 5], [14, 16, 11]]

Answer 4

Let's look at [2, 0, 1, 4, 3, 5]. In the cycle [2, 0, 1] the order of numbers really doesn't matter, so if you start from any of its point, you will get the cycle correctly.

An easy solution for an array of size N would be: 1. go through all indices 1..N-1 as starting_index 2. get the cycle beginning at index starting_index 3. if we have already seen this cycle, discard it. Otherwise, remember it.

The function might look like this:

def get_cycles(array):
    cycles = []
    for starting_index in range(len(array)):
        cycle = cycle_at(array, starting_index)
        if not any(are_equal(existing, cycle) for existing in cycles):
            cycles.append(cycle)
    return cycles

If you aren't familiar with any, the line with any does roughly this:

def any(iterable):
  for x in iterable:
    if x:
      return True
  return False

We want the cycles [0, 1, 2] and [1, 2, 0] to be considered equal. We can write a function that shifts one of them until it matches the second one:

def are_equal(cycle1, cycle2):
    if len(cycle1) != len(cycle2):
        return False
    for i in range(len(cycle1)):
        # [1, 2, 3, 4] -> [2, 3, 4, 1]
        cycle1 = cycle1[1:] + [cycle1[0]]
        if cycle1 == cycle2:
            return True
    return False

Or we can use the properties of these cycles and get:

def are_equal(cycle1, cycle2):
    return set(cycle1) == set(cycle2)

Because two cycles are equal if and only if they contain the same elements (order doesn't matter -- as the statement says).

Then we need to implement a function that would get the cycle starting at index i.

def cycle_at(array, index):
    visited_indices = set()
    cycle = []
    while True:
        cycle.append(index)
        visited_indices.add(index)
        index = array[index]
        if index in visited_indices:
            break
    return cycle

We need to remember which indices we visited, and we will store them in a set. Then we will 'follow the cycle' and traverse the array, adding the index to visited_indices every time we see a new index. If at any point we stumble upon a index we have already visited, we end the cycle.

You could improve the performance by not considering the indices that already occur in a cycle as starting indices, because this will eliminate the need for the are_equal function and will prevent you from finding the same cycle more than once.

Answer 5

You can keep track of all the indices you've already visited and ignore them next time. Also, each cycle will have unique indices and no matter where you start in a cycle(12 or 0, if both are in the same cycle), you can always complete the cycle(like a circle).

def gen_cycles(indices):
    cycles = []
    visited = []
    for i in indices:
        if(i in visited):
            continue
        start = i;
        current_cycle = []
        current_cycle.append(start)
        visited.append(start)
        j = indices[start]
        while(j!=start):
            current_cycle.append(j)
            visited.append(j)
            j = indices[j]
        cycles.append(current_cycle)
    return cycles

print(gen_cycles([12, 0, 8, 10, 9, 6, 5, 4, 13, 7, 17,14, 2,18, 16, 1, 11, 19, 3, 15]))

Output: [[12, 2, 8, 13, 18, 3, 10, 17, 19, 15, 1, 0], [9, 7, 4], [6, 5], [14, 16, 11]]

Answer 6

If an index is already part of a cycle you can just skip it.

def find_cycles(indices):
    """Given a list of indices return a list of cycles."""

    visited = set()
    cycles = []

    for start_ind in indices:

        if start_ind in visited:
            continue

        path = [start_ind]
        next_ind = indices[start_ind]

        while start_ind != next_ind:
            path.append(next_ind)
            next_ind = indices[next_ind]
        else:
            cycles.append(path)
            visited |= set(path)
    return cycles

find_cycles([12, 0, 8, 10, 9, 6, 5, 4, 13, 7, 17,14, 2,18, 16, 1, 11, 19, 3, 15])
# [[12, 2, 8, 13, 18, 3, 10, 17, 19, 15, 1, 0], [9, 7, 4], [6, 5], [14, 16, 11]]