Swap dla wielu zmiennych

0

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?

0

Możesz nie używać żadej. Zamiast tego użyć xora.
a ^= b
b ^= a
a ^= b

0

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.

Wygląda na to że tak.

Najpierw zauważ że na pewno można stworzyć funkcję swap(&x, &y) wykorzystującą tylko jedną dodatkową zmienną (albo, używając XOR-a, zero zmiennych).

Teraz, mając sekwencję docelową D
a, b, c, d, e ...

Oraz dowolną sekwencję wejściową W, dajmy na to
c, e, b, z, a ..

Działamy w taki sposób:

for I in <0; length(D) - 1):
    - N = indeks zmiennej a (pierwszego elementu D) w sekwencji W
    - zamień w sekwencji W element na pozycji N z elementem na pozycji I

Na razie ma to złożoność \theta(n<sup>2) (O(n</sup>2)), ale myślę że da się to doprowadzić co najmniej do złożoności \theta(n\log n) (O(n*log(n))).

0

Tezcatlipoca, po za faktem o którym wspomniałem wcześniej w komentarzu, twój algorytm ma jeszcze jedną zasadniczą wadę, przez co nie nadaje się do mojego zastosowania. może się źle wyraziłem wcześniej, ale ja nie chce, żeby zamieniał te zmienne na prawdę, ale jedynie zwrócił jak je zamienić. chce, aby przetłumaczył mi:
a, b, c, x, y = b, c, a, y, x
na coś takiego:

temp = a
a = b
b = c
c = temp
temp = x
x = y
y = temp

czyli dostał na input: {(a, b), (b, c), (c, a), (x, y), (y, x)} dawał możliwie jak najmniejszy output: {(temp, a), (a, b), (b, c), (c, temp), (temp, x), (x, y), (y, temp)}
tymczasem twoja metoda dała by output (w najlepszym wypadku):

swap (a, b)
swap (b, c)
swap (x, y)

czyli 9 przypisań. w sumie nie zależy mi bardzo na złożoności samego algorytmu, tylko żeby output był jak najprostszy.
ale jak wspomniałem w komentarzy, algorytm jest prawie gotowy i zaimplementowany. chce tylko znać odpowiedź na pytanie które zadałem...

1 użytkowników online, w tym zalogowanych: 0, gości: 1