Cycle decomposition in Python

Is there an algorithmically better way of doing this?

import numpy as np
l=np.random.permutation(10)
p=list(range(10))
print(l,p)
i=0
k=0
prod=1
z=0
def gcd(a, b):

while b:
a, b = b, a % b
return a
def lcm(a, b):

return a * b // gcd(a, b)

while z<10:
"""count how many times we have crossed (-1-ed) a number from p"""
k=0
while p[k]==-1 and k<9 :
"""find the first non -1 element in p (it's here that I feel that the code is especially clumsy) """

k=k+1
i=k
"""k is the first element in the cycle """
print(l[i])
p[k]=-1
z=z+1
j=1
while l[i]!=k:
"""go from i to l[i] until we get back to k, closing the cycle """
p[l[i]]=-1
z=z+1
i=l[i]
j+=1
"""g is just used to find the lcm """

print(l[i])
prod=lcm(prod,j)
print('------')
print(prod)


Use the built in gcd

In Python 3, you can just do:

from math import gcd


Consider keeping with the standard library

Instead of using np.random.permutation, consider just using random.shuffle to generate a random permutation. Removes the numpy dependency altogether.

Just use # instead of """

"""count how many times we have crossed (-1-ed) a number from p"""


Are usually used for docstrings, you are using them to elaborate on certain steps in an algorithm, I would use # for this.

Place the cycle decomposition into a function

The while loop introduces a lot of global variables and makes it hard to use, I would put the contents into a function. Also explain that this function displays a permutation as disjoint cycles.

Please use better names.

I'm still not sure what every variable does. Like why is p=list(range(10))? I would think p is short for permutation, but l seems to be what the actual permutation is. This program is really hard to understand simply because of your name choice.

There's room for improvement. Apart from what @Dair already suggested, I'd also recommend a few other changes.

Magic numbers

You're using 10 in many places, so why not defining it at the top of your program? (keep in mind that constants should be upper-cased)

Code style

This:

z = z + 1


Can be replaced by this:

z += 1


Since you're generating a shuffled list already, why not sort that to get the p ? So:

p = list(range(10))


Can become:

p = sorted(l)


While I understand the reason @Dair suggested shuffle instead of numpy, I'd suggest you keep it the way you did, as it's the fastest way you can get a shuffled list.

• One thing I would like to note: When I say "consider" I usually mean that there are reasons to disregard the advice I gave but you should, well, consider my point and decide whether it is right for situation. (This is regarding your last point and numpy)
– Dair
Commented Apr 25, 2017 at 16:26

In addition to what @Dair said (especially about variable names):

• You have a lot of hardcoded numbers in there (going from 10 to some other upper limit means replacing quite a few other numbers). Better keeping those in a constant like UPPER_LIMIT = 10 and using that.
• You don't need that while p[k]==-1 and k<9 : loop. You know which element is the first -1 because you're the one setting it, just keep track of the index and you're good to go (BTW, what if you had a million elements, would you go through all of them every time?).

I didn't test it thoroughly, but this should give you the same result without that loop:

k = 0
while z < 10:
i = k
print(l[i])
p[k] = -1
z = z+1
j = 1
old_k = k
k_set = False
while l[i] != old_k:
p[l[i]] = -1
k += 1
z += 1
i = l[i]
j += 1
print(l[i])
prod = lcm(prod,j)
print('------')

print(prod)

• thanks, but you are wrong in the second point (the first element, after the one that is set to -1 at the end of the inner while loop, may be a -1 already)
– Nesa
Commented Apr 25, 2017 at 13:18
• I see. In that case you should still consider what I said: keep track of the minimum index of the element that is not -1. As I said, you're the one setting it, so you can do that. Commented Apr 25, 2017 at 14:37
• I don't think that's possible, consider a permutation where by my method we -1 out the following elements during the first cycle: 0,8,7,6,5,4 , so the minimal element that is not -1is 1, then after we cross out 2 and 3 how do we know if 9 is still there? I don't know if my approach would run faster if we did it with a set instead of 1-ing in a list like here: gist.github.com/begriffs/2211881
– Nesa
Commented Apr 25, 2017 at 16:53