Permutationen: Prüfungszyklus Notation

Question

Bitte beachten Sie, folgendes Problem: Ich habe eine bestimmte Permutation Sigma:

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

das gewünschte Ergebnis ist der Zyklus-Notation zu erzeugen, die folgt:

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

Mein Versuch geht Wie der Code unten scheint, scheint es, dass ich nur bis zum ersten Zyklus komme, aber nicht wieder in den zweiten eingreifen kann:

Die Idee hinter der my_row_cycle-Funktion ist eine bestimmte Permutation Sigma zu nehmen, eine Art Leistungsschalter namens Marker (Cricket geschlossen, wenn Marker == 0), und durchlaufen die Permutation, bis ich einen Zyklus zu vervollständigen, sobald der Zyklus abgeschlossen ist, speichern ich es in einer Liste.

Ich überprüfe dann, ob es noch andere Zyklen gibt, aus der Permutation zu extrahieren, indem ich wieder über Sigma iteriere, bis ich eine Zahl in Sigma finde, die nicht in den vorher extrahierten Zyklen ist. Wenn eine solche Nummer gefunden wird, starte ich den Prozess neu. Wenn nicht, stoße ich meinen Schutzschalter ab, markiere == 1, um den gesamten Prozess zu beenden und gebe meine Zyklusnotation der Sigma-Permutation aus.

aber das scheint immer noch Utopie für mich zu sein. :)

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 

nach Auswertung:

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

kann ich nicht scheinen zu verstehen, warum meine Marker Reisen auf den Wert „1“, und doch meinen Zyklus Notation unvollständig sind. Ich danke Ihnen im Voraus, wenn Sie irgendwelche Vorschläge und oder Korrekturen haben.

Answer 1

Könnte es sein, weil Sie versehentlich die variablen a mehrere Male in Ihrem verschachtelten Schleifen verwenden:

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 separate Variablennamen alle verschiedenen Iterationen.

Answer 2

Ich glaube, diese Funktion tut, was Sie wollen:

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