Finding Cycles In A Dictionary

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

Solution 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:

deffind_cycles(m):
    n = m.copy()  # don't mutilate the original
    cycles = []
    while n:
        visited = {}
        count = 0
        k, v = n.popitem()
        while v isnotNone:
            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 incycle)
            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

Solution 2:

Edited Hey you have to just replace the pair with any other symbol in the list once it is found. Then it gives you the desired results.

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

k = list(map.items())

print(k)

result = []

for i in k:
    if i != -1and i[::-1] in k:
        result.append((set(i)))
        k[k.index(i[::-1])] = -1print(result)
#if you want tuples as output
[print(tuple(x),end = " ") for x in result]