Count cycles in a permutated list

user_18113322 0
Viewed 113

I am trying to make a function that counts the number of cycles within a permutated list.

I do sometimes get the right answer when running the code, but most times I receive an error message - and I am unable to figure out why.

My code is as follows:

def count_cycles(n):

    cycle_count = 0
    copy_list = []
    
    for element in n:
        copy_list.append(element)

    while len(copy_list) != 0:
        ran_num = random.choice(copy_list)

        while True:
            if n[ran_num] == ran_num:
                cycle_count = circle_count + 1
                if int(ran_num) in copy_list:
                    copy_list.remove(ran_num)
                    
                break
            
            else:
                n.insert(ran_num, ran_num)
                print(n, ran_num, copy_list)
                ran_num = n[ran_num + 1]
                
                print(ran_num)
                copy_list.remove(ran_num)
                    
                n.remove(ran_num)
                continue

    return print(cycle_count, n)

What I use is that I test with this permutated list with 3 cycles [2, 6, 0, 3, 1, 4, 5].

Picture of output from a correct and incorrect run

I used print(n, ran_num, copy_list) to assess the output as per the picture.

permutation list algorithm python
2 Answers

Here is one possibility:

p = [2, 6, 0, 3, 1, 4, 5]

cycles = set()
elts = set(range(len(p)))
while elts:
    cycle = []
    x0 = elts.pop()
    cycle.append(x0)
    x = p[x0]
    while x != x0:
        cycle.append(x)
        x = p[x]
    elts -= set(cycle)
    cycles.add(tuple(cycle))
    
print(cycles)

It gives:

{(0, 2), (1, 6, 5, 4), (3,)}

Then to get the number of cycles you can use len(cycles).

user_151877280

In addition to the existing answer, sympy provides some functionality to work with permutations. In this case, you could use the following:

from sympy.combinatorics import Permutation
p = Permutation([2, 6, 0, 3, 1, 4, 5])
num_cycles = p.cycles # 3
user_45859630
Related