Wie Sie vielleicht wissen, hat Python Listen. Wie Sie vielleicht nicht wissen, können sich diese Listen selbst enthalten.

a = []
a.append(a)

Python 2

Python 3

Diese sind cool und es gibt viele interessante Dinge, die Sie damit machen können, die Sie jedoch nicht vergleichen können.

a = []
a.append(a)
b = []
b.append(b)
a == b

Python 2

Python 3

Aufgabe

Ihre Aufgabe ist es, eine Funktion in Python (oder einer beliebigen Sprache, die Python-Objekte direkt verarbeiten kann) zu schreiben, die zwei Listen aufnimmt, die sich möglicherweise selbst enthalten, und diese vergleicht.

Zwei Listen sind gleich, wenn sie gleich lang sind und es keine Folge von Zahlen gibt, so dass die Indizierung beider Listen nach dieser Folge zu zwei Objekten führt, die unter dieser Definition von gleich nicht gleich sind. Alle in einer Liste enthaltenen Nicht-Listenobjekte sind der Einfachheit halber Python-Ganzzahlen und sollten mit der in Python integrierten Gleichheit für Ganzzahlen verglichen werden.

Ihr Programm sollte sich nicht auf die Rekursionstiefe von Python verlassen, um festzustellen, ob eine Liste unendlich tief ist. Das ist:

def isInfinite(a,b):
 try:
  a==b
  return False
 except RunTimeError:
  return True

Ist keine gültige Methode, um festzustellen, ob zwei Listen selbstreferenziell sind.

Testfälle

Angenommen, Sie definieren eine Funktion equal

a = []
a.append(a)
b = []
b.append(b)
print(equal(a,b))

True

a = []
b = []
a.append(b)
b.append(a)
print(equal(a,b))

True

a = []
b = []
a.append(1)
a.append(b)
b.append(1)
b.append(a)
print(equal(a,b))

True

a = []
a.append(a)
b = [a]
print(equal(a,b))

True

a = []
b = []
c = []
a.append(b)
b.append(c)
c.append(a)
equal(a,b)

True

a=[1,[2]]
b=[1,[2,[1]]]
a[1].append(a)
b[1][1].append(b[1])

True

a = []
a.append(a)
b = [1]
b.append(a)
c = [1]
c.append([c])
print(equal(b,c))

False

a = []
b = []
a.append(1)
a.append(b)
b.append(a)
b.append(1)
print(equal(a,b))

False

a = []
b = []
a.append(a)
b.append(b)
b.append(b)
print f(a,b)

False

Python 2 , 94 Bytes

g=lambda c,*p:lambda a,b:c in p or all(map(g((id(a),id(b)),c,*p),a,b))if a>[]<b else a==b
g(0)

Probieren Sie es online!

Eine Verbesserung gegenüber der sehr cleveren Lösung von isaacg, die verarbeiteten Listenpaare zu speichern idund für gleich zu erklären, wenn derselbe Vergleich auf einer niedrigeren Ebene erfolgt.

Der rekursive Schritt all(map(...,a,b))besagt, dass aund bgleich sind, wenn alle entsprechenden Elementpaare in ihnen gleich sind. Dies funktioniert gut, um ungleiche Längen abzulehnen, da mapdie kürzeste Liste mit aufgefüllt wird None, im Gegensatz zu zipdenen , die abgeschnitten werden. Da keine der tatsächlichen Listen enthält None, werden diese aufgefüllten Listen immer zurückgewiesen.

Python, 233 218 197 217 Bytes

d=id
def q(a,b,w):
 w[(d(a),d(b))]=0
 if d(a)==d(b):return 1
 if(a>[]and[]<b)-1:return a==b
 if len(a)!=len(b):return 0
 for x,y in zip(a,b):
  if((d(x),d(y))in w or q(x,y,w))-1:return 0
 return 1
lambda a,b:q(a,b,{})

Die anonyme Funktion in der letzten Zeile führt die gewünschte Funktion aus.

Dies ist noch in der Entwicklung, ich wollte nur zeigen, dass dies möglich ist.

Im Wesentlichen setzen wir einen Eintrag in w, wenn wir an einem bestimmten Scheck arbeiten. Zwei Dinge sind gleich, wenn sie dasselbe Objekt sind, wenn sie keine Listen sind und wenn sie gleich sind oder wenn alle ihre Elemente gleich sind oder bearbeitet werden.