Witam.
Próbuje stworzyć algorytm, który zamieni mi wartościami wiele zmiennych. Chodzi mi o coś w stylu pythonowego:
a, b, c, d, e = b, c, d, b, c
Z analizowanych przykładów wywnioskowałem, że aby zrobić dowolną wariację potrzeba nie więcej jak jednej zmiennej pomocniczej. Zastanawiam się, czy to jest prawdziwe zawsze? Może jest jakieś twierdzenie o tym? (nie umiałem wyszukać) Od tego czy to prawda zależy jak dalej będzie wyglądał mój algorytm.
Algorytm działa na takiej zasadzie:
Tworzę graf skierowany, którego wierzchołkiem jest każda zmienna {a, b, c, d, e}, a krawędzie {(a, b), (b, c), (c, d), (d, b), (e, c)} reprezentują przypisania. Następnie usuwam cykle z tego grafu w ten sposób: przeszukuje graf wgłąb i jeśli znajdę cykl, np.: b -> c -> d -> b, to usuwam krawędź (d, b) i w zależności od tego, czy b ma rodzica (ma a), to albo tworzę krawędź (d, b.rodzic)* albo (d, temp), gdzie temp=b i to przypisanie robię na początku. *Dociekliwy zauważy, że przy (d, b.rodzic) powstanie znowu cykl, ale przeszukiwanie wgłąb już go nie wykryje, a taki cykl prawidłowo przypisze zmienne, bez potrzeby tworzenia zmiennej tymczasowej. Potem wykonuje przeszukiwanie wszerz, aby przypisać wartości w odpowiedniej kolejności.
Tak więc zmiennych tymczasowych powinno być maksymalnie tyle, ile cykli jest w podgrafie z największą ilością cykli. Wydaje mi się, że jeśli graf podstawowy jest spójny, graf nie ma pętli oraz każda krawędź ma tylko jednego potomka, to maksymalna ilość cykli to 1. Czy to prawda?