3
\$\begingroup\$

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)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Could you post the code before minification? \$\endgroup\$ Commented Apr 24, 2017 at 23:04
  • \$\begingroup\$ By "doing this" you mean computing the permutation order using its cycle decomposition, right? \$\endgroup\$ Commented Apr 24, 2017 at 23:15
  • \$\begingroup\$ @le_m yes, I haven't minified the code \$\endgroup\$ Commented Apr 25, 2017 at 13:02
  • \$\begingroup\$ gist.github.com/begriffs/2211881 this is a much faster algorithm \$\endgroup\$ Commented May 4, 2017 at 17:30

3 Answers 3

Reset to default
7
\$\begingroup\$

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 """

Comments such as:

"""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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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) \$\endgroup\$ Commented Apr 25, 2017 at 16:26
2
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ 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) \$\endgroup\$ Commented Apr 25, 2017 at 13:18
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Apr 25, 2017 at 14:37
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Apr 25, 2017 at 16:53

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.