Entscheiden, ob zwei Listen zyklische Permutationen voneinander sind

Question

Ich wurde zugewiesen, um eine Funktion zu schreiben, die zwei Listen akzeptiert und gibt True zurück, wenn die andere Liste eine zyklische Permutation der anderen ist. Ich schrieb eine Funktion, die zwei Listen und Änderungen zwischen dem ersten und letzten Platz akzeptiert. Danach habe ich eine Funktion geschrieben, die die erste Funktion mit einer for-Schleife aufruft und am Ende der Schleife True zurückgibt, wenn sie für jedes i zutrifft. ich versucht Ausführung des Codes und ive traf auf mehrere Fehlermeldungen:

Datei "C: /WinPython-64bit-3.5.2.2Qt5/settings/.spyder-py3/temp.py", Zeile 13, in zyklischen wenn change_position (LST1, LST2):

Datei "C: /WinPython-64bit-3.5.2.2Qt5/settings/.spyder-py3/temp.py", Zeile 5, in change_position LST3 [0] = lst4 [ len (lst4)]

Hier ist mein Code:

def change_position(lst3, lst4): 
    if len(lst3) != len(lst4): 
     print(False) 
    else: 
     lst3[0] = lst4[len(lst4)] 


def cyclic(lst1, lst2): 
    if len(lst1) != len(lst2): 
     print(False) 
    else: 
     for i in range(len(lst1)): 
      if change_position(lst1, lst2): 
       print(True) 
      else: 
       print(False) 
cyclic([1, 2, 3, 4], [4, 1, 2, 3]) 

Weiß jemand, wie ich das beheben kann, damit die Funktion funktioniert? Vielen Dank im Voraus für Ihre Hilfe.

Answer 1

Keine Notwendigkeit, Ihre Liste neu zu ordnen, werden mit 0

def is_cyc_perm (list1, list2): 
    if len (list1) == len (list2): 
     for shift in range (len (list1)): 
      for i in range (len (list1)): 
       if list1 [i] != list2 [(i + shift) % len (list1)]: 
        break 
      else: 
       return True 
     else: 
      return False 
    else: 
     return False 


print (is_cyc_perm ([8, 2, 5, 7], [8, 2, 5, 7])) 
print (is_cyc_perm ([7, 8, 2, 5], [8, 2, 5, 7])) 
print (is_cyc_perm ([2, 5, 7, 8], [8, 2, 5, 7])) 
print (is_cyc_perm ([8, 5, 2, 7], [8, 2, 5, 7])) 
print (is_cyc_perm ([7, 2, 5, 8], [8, 2, 5, 7])) 
print (is_cyc_perm ([8, 2, 5, 3], [8, 2, 5, 7])) 

Answer 2

nur Berechnungen Index tun beginnt der Listenindex, sollten Sie Bereich (0, len (Liste) -1) verwenden.

def change_position(lst3, lst4): 
    if len(lst3) != len(lst4): 
     print(False) 
    else: 
     lst3[0] = lst4[len(lst4)-1] 


def cyclic(lst1, lst2): 
    if len(lst1) != len(lst2): 
     print(False) 
    else: 
     for i in range(len(lst1)-1): 
      if change_position(lst1, lst2): 
       print(True) 
      else: 
       print(False) 

Answer 3

Das Rotieren einer doppelt verketteten Liste ist eine schnelle Operation mit Zeigern. Sie können alle Rotationen einfach versuchen, wenn es eine Übereinstimmung gibt.

Das Collections-Modul bietet auch Counter, die für einen schnellen Test verwendet werden kann, wenn beide Listen die gleiche Anzahl der gleichen Elemente haben. Es ist nur eine stärkere Version der offensichtlichen Überprüfung derselben Länge.

import collections 

def is_cyc_perm(seq1, seq2): 
    mset1 = collections.Counter(seq1) 
    mset2 = collections.Counter(seq2) 
    if mset1 != mset2: 
     return False 

    size = len(seq1) 
    deq1 = collections.deque(seq1) 
    deq2 = collections.deque(seq2) 
    for _ in range(size): 
     deq2.rotate() 
     if deq1 == deq2: 
      return True 
    return False