Algorytm na permutacje bez rekurencji

Question

Witam.

Od pewnego czasu próbuję napisać algorytm to wypisywania permutacji w porządku leksykograficznym bez rekurencji. Nie mam pojęcia jak to zrobić, a w sieci same rekurencje. Może znacie taki algorytm.

Comments

Się tak spytam, a czemu nie chcesz rekurencji ?

---

Bo ma ograniczony stos i jeszcze nie widziałem nierekurencyjnego rozwiązania.

Answer 1

1. Robisz sortowanie po pierwszym indeksie tablic permutacji

2. Grupujesz te tablice, których wartość pierwszego indeksu była taka sama.

3. Sortujesz po drugim indeksie utworzone grupy (pozostałe tablice są na swoich miejscach już)

4. Znowu tworzysz ewentualne grupy i sortujesz po kolejnym indeksie.

Przestajesz, kiedy nie utworzysz już żadnej grupy.

Nie wiem, czy to dobry pomysł, wydaje mi się w porządku. :) Nie wiem też, czy jasno się wyraziłem, więc pytaj. Czekam też na ewentualne uwagi do tego pomysłu.

Comments

Jeżeli robisz zadanie na SPOJu z permutacji http://pl.spoj.com/problems/TPERM2/  to uważaj i nie wtop  tak jak ja. Męczyłem się też z tym algorytmem dość długo a jak już zrobiłem to się okazało że jedynym dostępnym językiem dla tego zadania jest C.

---

Rozumiem że twój sposób jest na posortowanie wygenerowanych permutacji na kolejność leksykograficzną a pytanie brzmi jak te permutacje wygenerować.

---

Aaa, no to nie sprecyzowałeś, bo w pytaniu jest mowa o wypisywaniu permutacji, nie o ich generowaniu. :) Jak coś wymyślę, to tutaj zamieszczę.

---

https://en.wikipedia.org/wiki/Heap%27s_algorithm

Tutaj masz wersję iteracyjną- tylko będziesz musiał sobie to przepisać do C/C++

---

Dzięki.