CODEWITHSUNDEEP
pythonsage
Yann1123
Yann1123

Reputation: 21

Permutations: producing cycle notation

Please consider the following problem: I have a certain permutation sigma:

sigma = [4,1,6,2,3,5]

the desired result is to produce the cycle notation which follows:

my_cycles_perm = [[4,2,1],[6,5,3]]

My attempt goes as per the code below, however it seems I only get as far as the first cycle but can't seem to reengage into the second one:

The idea behind the my_row_cycle function is to take a certain permutation sigma, set up a sort of circuit breaker called marker(crcuit closed when marker == 0), and iterate over the permutation until I complete a cycle, once the cycle is complete I store it into a list.

I then verify if there are still other cycles to extract from the permutation by iterating over sigma again until I find a number in sigma that isn't in the cycles extracted prior. If such a number is found I restart the process. If not I trip my circuit breaker, marker == 1 to end the entire process and output my cycle notation of the sigma permutation.

but this still seems to be utopia for me. :)

def my_row_cycle(sigma):
    aux_sigma = list(sigma)
    init_ref = aux_sigma.index(aux_sigma[0]) +1       #First antecedent of aux_sigma
    init_image = aux_sigma[init_ref-1]                #Image of the antecedent
    jumper_image = init_image
    row_cycle = []
    row_cycle.append(init_image)
    my_cycles_perm = []

    marker = 0

    while marker == 0:                                 #Circuit breaker
        while jumper_image != init_ref:                #establishes if cycle complete
            for x in aux_sigma:                     #iterates sigma while cycle incomplete
                jumper_ref = aux_sigma.index(x) + 1
                if jumper_ref == jumper_image:         #Condition to append to cycle
                    row_cycle.append(x)
                    jumper_image = x                   #Changing the while loop condition
        my_cycles_perm.append(row_cycle)

        for a in aux_sigma:
            for a in my_cycles_perm:
                cycle = a
                for a in cycle:                  #looking for match in aux_sigma and cycle
                    if a not in cycle:
                        row_cycle = []
                        init_image = a
                        init_ref = aux_sigma.index(init_image) + 1
                        marker = 0
                        break

                    else:
                        marker = 1

return init_ref, init_image, jumper_image, jumper_ref, row_cycle, marker, my_cycles_perm

after evaluation:

(1, 4, 1, 6, [4, 2, 1], 1, [[4, 2, 1]])

I can't seem to understand why my marker trips to the value "1" and yet my cycle notation is incomplete. I thank you in advance if you have any suggestions and or corrections.

Upvotes: 2

Views: 3823

Answers (4)

Latos
Latos

Reputation: 1

Here is another solution making advantage of the dict.popitem() and dict.pop() functions, given that the ordering of cycles is not important:

def cycles(permutation):
    # Dictionary of non-trivial mappings
    dic = {i:j for i, j in enumerate(permutation) if i != j}

    cycles = []
    current = []

    while len(dic) > 0:
        if current == []:
            current = [*dic.popitem()]

        i = current[-1]
        j = dic.pop(i)

        if j in current:
            cycles.append(tuple(current))
            current = []
        else:
            current.append(j)

    return tuple(cycles)

Upvotes: 0

DroneBetter
DroneBetter

Reputation: 33

Trivial reduction of BallpointBen's answer

def to_cycles(perm):
    pi={i+1: p for i,p in enumerate(perm)}
    cycles=[]
    while pi:
        next_item=pi[next(iter(pi))]
        cycle=[] #arbitrary starting element
        while next_item in pi:
            cycle.append(next_item)
            next_item=pi[next_item]
            del(pi[cycle[-1]])
        cycles.append(cycle)
    return(cycles)

Upvotes: 1

BallpointBen
BallpointBen

Reputation: 13820

I believe this function does what you wish:

def to_cycles(perm):
    pi = {i+1: perm[i] for i in range(len(perm))}
    cycles = []

    while pi:
        elem0 = next(iter(pi)) # arbitrary starting element
        this_elem = pi[elem0]
        next_item = pi[this_elem]

        cycle = []
        while True:
            cycle.append(this_elem)
            del pi[this_elem]
            this_elem = next_item
            if next_item in pi:
                next_item = pi[next_item]
            else:
                break

        cycles.append(cycle)

    return cycles

print(to_cycles([]))
# []

print(to_cycles([1]))
# [[1]]

print(to_cycles([4,1,6,2,3,5]))
# [[4, 2, 1], [6, 5, 3]]

Upvotes: 4

harfel
harfel

Reputation: 296

Could it be because you accidentally use the variable a multiple times in your nested loops:

for a in aux_sigma :
    for a in my_cycles_perm :
        cycle = a
        for a in cycle :        # <<-- a iterates ovr cycles, so
            if a not in cycle : # <<-- a in cycle is alsways true
                # [...]
                marker = 1
            else :
                marker = 0

Assign seperate variable names to all distinct iterations.

Upvotes: 0

Related Questions