python - Finding cycles in a dictionary

Question

I have a dictionary which has values as:

m = {1: 2, 7: 3, 2: 1, 4: 4, 5: 3, 6: 9}

The required output should be cyclic values like 1:2 -> 2:1 = cycle, which both are present in dictionary. 4:4 is also a cycle.

My output should be

[(1, 2), [4]]

CODE

m = {1: 2, 7: 3, 2: 1, 4: 4, 5: 3, 6: 9}
k = list(m.items())
print(k)

p = [t[::-1] for t in k]
print(p)

my_list = [(a, b) for (a, b) in p for (c, d) in k  if ((a ==c) and (b == d))]

for i in k:
     if i in my_list:
             print("cycles : ", i)

OUTPUT:

The output I am getting is

cycles : (1, 2)
cycles : (2, 1)
cycles : (4, 4)

Can someone help me out with this?

Answer 1

Let's split this into two steps. First we'll find the cycles. Then we'll format the output however you want.

Finding cycles is easy, given that you have a dictionary: values become keys, making lookup fast. We can store the cycles in sorted order in a set to avoid duplicates:

cycles = set()
for k, v in m.items():
    if m.get(v) == k:
        cycles.add(tuple(sorted((k, v))))

Not that I'd recommend it, but the above can be written as an illegible one-liner:

cycles = set(tuple(sorted(item)) for item in m.items() if m.get(item[1]) == item[0])

Now to format the data. You want a list output, and entries with duplicates formatted as lists:

output = [[k] if k == v else (k, v) for k, v in cycles]

If you don't like clean code, you can imagine how to turn the whole operation into a one-liner :)

Update

It's worth considering the case where cycles are longer than one or two entries. You seem to want to store only one element per cycle, so let's do that. We can follow the chain from each element in the dictionary. If any part of the chain makes a cycle, we can find the minimum element of the cycle to report, and remove all the visited elements, since they are all no longer under consideration:

def find_cycles(m):
    n = m.copy()  # don't mutilate the original
    cycles = []
    while n:
        visited = {}
        count = 0
        k, v = n.popitem()
        while v is not None:
            visited[k] = (count, v)
            count += 1
            k = v
            v = n.pop(k, None)

        if k in visited:
            cycle_start = visited[k][0]
            item = min((k, v) for k, (c, v) in visited.items() if c >= cycle_start)
            cycles.append(item)

    return [[k] if k == v else (k, v) for k, v in cycles]

For example:

>>> find_cycles({1:2, 2:3, 3:4, 4:5, 5:1, 6:1, 7:1, 8:8})
[(1, 2), [8]]

A better generalization might be to return a tuple with the entire cycle in it, starting with the smallest key. Mostly the statements under if k in visited: need to change to do that:

    visited[k] = count
    ...
    if k in visited:
        if len(visited) == 1:
            cycle = list(visited.keys())
        else:
            cycle_start = visited[k]
            cycle = sorted((c, k) for k, c in visited.items() if c >= cycle_start)
            cycle = tuple(k for c, k in cycle)
            k = min(range(len(cycle)), key=lambda x: cycle[x])
            cycle = cycle[k:] + cycle[:k]
       cycles.append(cycle)

return cycles

This version is more informative:

>>> find_cycles({1:2, 2:3, 3:4, 4:5, 5:1, 6:1, 7:1, 8:8})
[(1, 2, 3, 4, 5), [8]]

Here is my IDEOne scratchspace in case you're interested: https://ideone.com/6kpRrW