Jernej - 1 year ago 108
Python Question

# efficiently converting a bijection to cycle notation

Consider the following problem. Given is an array P of length n representing a bijection. That is element 0 <= i < n is mapped to P[i].

Given that P is a permutation, it can be written in cycle notation as described for example here.

For example if

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

then the result in cycle notation would be

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

Following is a Python method accomplishing this

``````def toCycle(p):
covered = cur = 0
perm = []
n = len(p)
done = [0]*n
while covered < n:
while cur < n and done[cur] == -1:
cur+=1
cycle = [p[cur]]
sec = p[p[cur]]
done[p[cur]] = -1
done[cur] = -1
covered+=1
while sec != cycle[0]:
cycle.append(sec)
done[sec] = -1
sec = p[sec]
covered+=1
perm+=[tuple(cycle)]
return perm
``````

The algorithm clearly runs in linear time (each element of done/p is accessed a constant number of times) and hence there is not much that can be done asymptotically.

As I have to use this method on a large number of large permutations I was wondering

Can you make it faster? Do you have any suggestions for performance
improvement?

``````def cycling(p, start, done):
while not done[e]:
done[e] = True
e = p[e]
yield e

def toCycle(p):
done = [False]*len(p)
cycles = [tuple(cycling(p, 0, done))]
while not all(done):
start = done.index(False)
cycles.append(tuple(cycling(p, start, done)))
return cycles
``````

With your example my code runs about 30% faster than yours.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download