Dzieje się tak dlatego, że algorytm jest nieprawidłowy. Problem z twoim algorytmem polega na tym, że zależy on od krawędzi, od których zaczynamy tworzyć listę ciał. Aby to wyjaśnić, weźmy prosty przykład wykresu z 4 krawędziami jako - edges = [('1','2'),('2','3'),('3','4'),('1','4')].
Pierwszy przypadek -
>>> edges = [('1','2'),('2','3'),('3','4'),('1','4')]
>>> bodylist = []
>>> for edge in edges:
... #If at least one node of the edge is anywhere in bodylist, append the new nodes to that list.
... try:
... index = [i for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body][0]
... bodylist[index].append(edge[0])
... bodylist[index].append(edge[1])
... #If not, make a new list containing the new nodes.
... except:
... bodylist.append([edge[0], edge[1]])
...
>>> print([set(x) for x in bodylist])
[{'4', '1', '3', '2'}]
dostać jedno ciało z wierzchołków - 1, 2, 3, 4. Czemu?
Po rozpoczęciu pracy z (1,2) dodano to do listy karoserii. Potem wziąłeś (2,3), widzisz, że 2 jest już w pozycji dodanej na liście ciał, dodajesz ją ponownie do tej samej i to się dzieje, a wszystkie są dodawane do tego samego ciała.
Teraz możemy przyjmować te same krawędzie w innej kolejności - edges = [('1','2'),('3','4'),('2','3'),('1','4')]. Okazuje się, że -
>>> edges = [('1','2'),('3','4'),('2','3'),('1','4')]
>>> bodylist = []
>>> .... #same logic
>>> print([set(x) for x in bodylist])
[{'4', '1', '3', '2'}, {'4', '3'}]
Jak widać, tym razem masz dwa różne ciała (i oczywiście nie mają racji) Dlaczego?
Znów zacząłem od (1,2), dodałem to do bodylist jako ciało, następnie wziąłeś (3,4), sprawdzając to, widzisz, że żaden z wierzchołków nie jest już w żadnym ciele, stąd dodałeś to do osobnego ciała. Biorąc trzeci element (2,3), widzimy, że jest on tam zarówno w pierwszym, jak i drugim ciele, ale twoja logika polega po prostu na zabraniu pierwszego ciała i dodaniu do tego elementu. (Czy widzisz gdzie idziesz źle?)
To dlaczego uzyskać różne wyniki, kiedy przetasować listę, a kolejność jest ważna dla logiki (co jest źle).
To, co musisz zrobić, to, że jeśli znajdziesz wierzchołki dla krawędzi w wielu ciałach, musisz scalić oba ciała w jedno ciało.
Kolejna rada, nie trzeba dodawać list do bodylist zamiast możemy użyć sets dla każdego body.
Roztwór próbki będzie wyglądać -
from random import shuffle
edges = [('7', '9'), ('2', '8'), ('4', '10'), ('5', '9'), ('1', '2'), ('1', '6'), ('6', '10')]
bodylist = []
shuffle(edges)
for edge in edges:
bodies = [body for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body]
if len(bodies) > 0:
tempset = {edge[0],edge[1]}
for x in bodies:
tempset.update(x)
print('tempset :',tempset)
bodylist.remove(x)
bodylist.append(tempset)
else:
bodylist.append({edge[0],edge[1]})
print([set(x) for x in bodylist])
Co masz na myśli inną odpowiedź? Różni się od czego? –
Być może nie rozumiem tego ... Generalnie otrzymasz inną odpowiedź, kiedy przetasujesz listę, nie? Czy też mówisz, że tasuje krotki na twojej liście, a nie tylko kolejność krotek? – Stiffo
Wynikiem jest zestaw niepołączonych ciał, a ten zestaw zmienia się za każdym razem, gdy tasuje się krawędzie. Powinien być niezależny od zamówienia. –