Rozważamy zbiór: \(\displaystyle{ \left\{ 1,2,3,...,n\right\}}\), wypisujemy permutacje w porządku leksykograficznym i.. ma ktoś pomysł na algorytm znajdujący:
(a) środkową permutację
(b) \(\displaystyle{ m}\)-tą permutację, dla zadanego \(\displaystyle{ m}\)
(c) którą permutacją w porządku leksykograficznym jest zadana permutacja ?
w jakim tam będę chciał to później języku napisać to może być różnie, najwazniejsza jest dla mnie teoria.. macie jakieś pomysły, bądź ciekawe linki? oczywiście nie mówimy o rozwiązaniu generującym następną permutację po zadanej..
[Algorytmy] Znajdowanie permutacji
-
norwimaj
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
[Algorytmy] Znajdowanie permutacji
c)
Na przykładzie \(\displaystyle{ 2,4,7,3,1,5,8,6}\).
Pierwsza stoi dwójka. Jest \(\displaystyle{ (n-1)!=7!}\) permutacji zaczynających się na \(\displaystyle{ 1}\) i one wszystkie są mniejsze w porządku leksykograficznym niż dana permutacja. Oprócz tego trzeba doliczyć niektóre permutacje zaczynające się od \(\displaystyle{ 2}\), ale to zrobimy w kolejnych obrotach pętli.
W drugim obrocie pętli patrzymy na permutację \(\displaystyle{ 4,7,3,1,5,8,6}\) zbioru \(\displaystyle{ 1,3,4,5,6,7,8}\).
Musimy policzyć wszystkie permutacje zaczynające się od \(\displaystyle{ 1}\) lub \(\displaystyle{ 3}\). Jest ich \(\displaystyle{ 2\cdot 6!}\).
W trzecim obrocie pętli mamy permutację \(\displaystyle{ 7,3,1,5,8,6}\) i do wyniku dopisujemy \(\displaystyle{ 4\cdot 5!}\), bo zostały nam do wykorzystania \(\displaystyle{ 4}\) liczby mniejsze od \(\displaystyle{ 7}\).
W ten sposób dostajemy wynik \(\displaystyle{ 1\cdot7!+2\cdot6!+4\cdot5!+\ldots = (\ldots((1\cdot7+2)\cdot6+4)\cdot5+\ldots )}\).
Jedynym problemem jest szybkie policzenie liczb pozostałych do wykorzystania, mniejszych od danej liczby. Można założyć, że \(\displaystyle{ n=2^k}\), bo zawsze można \(\displaystyle{ n}\) powiększyć. Wtedy konstruujemy drzewo binarne o \(\displaystyle{ n}\) liściach, każdy liść na tej samej głębokości. Liście etykietujemy kolejno \(\displaystyle{ 1,2,3,\ldots,2^k}\). W każdym wierzchołku drzewa trzymamy informację, ile niewykorzystanych liczb znajduje się w lewym poddrzewie. W ten sposób operacje na drzewie zajmują czas \(\displaystyle{ \Theta(\log n)}\) za każdym obrotem pętli, czyli cały algorytm ma czas \(\displaystyle{ \Theta(n\log n)}\).
Na przykładzie \(\displaystyle{ 2,4,7,3,1,5,8,6}\).
Pierwsza stoi dwójka. Jest \(\displaystyle{ (n-1)!=7!}\) permutacji zaczynających się na \(\displaystyle{ 1}\) i one wszystkie są mniejsze w porządku leksykograficznym niż dana permutacja. Oprócz tego trzeba doliczyć niektóre permutacje zaczynające się od \(\displaystyle{ 2}\), ale to zrobimy w kolejnych obrotach pętli.
W drugim obrocie pętli patrzymy na permutację \(\displaystyle{ 4,7,3,1,5,8,6}\) zbioru \(\displaystyle{ 1,3,4,5,6,7,8}\).
Musimy policzyć wszystkie permutacje zaczynające się od \(\displaystyle{ 1}\) lub \(\displaystyle{ 3}\). Jest ich \(\displaystyle{ 2\cdot 6!}\).
W trzecim obrocie pętli mamy permutację \(\displaystyle{ 7,3,1,5,8,6}\) i do wyniku dopisujemy \(\displaystyle{ 4\cdot 5!}\), bo zostały nam do wykorzystania \(\displaystyle{ 4}\) liczby mniejsze od \(\displaystyle{ 7}\).
W ten sposób dostajemy wynik \(\displaystyle{ 1\cdot7!+2\cdot6!+4\cdot5!+\ldots = (\ldots((1\cdot7+2)\cdot6+4)\cdot5+\ldots )}\).
Jedynym problemem jest szybkie policzenie liczb pozostałych do wykorzystania, mniejszych od danej liczby. Można założyć, że \(\displaystyle{ n=2^k}\), bo zawsze można \(\displaystyle{ n}\) powiększyć. Wtedy konstruujemy drzewo binarne o \(\displaystyle{ n}\) liściach, każdy liść na tej samej głębokości. Liście etykietujemy kolejno \(\displaystyle{ 1,2,3,\ldots,2^k}\). W każdym wierzchołku drzewa trzymamy informację, ile niewykorzystanych liczb znajduje się w lewym poddrzewie. W ten sposób operacje na drzewie zajmują czas \(\displaystyle{ \Theta(\log n)}\) za każdym obrotem pętli, czyli cały algorytm ma czas \(\displaystyle{ \Theta(n\log n)}\).
-
adambak
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[Algorytmy] Znajdowanie permutacji
po prostu genialne
co do podpunktu (b) (no bo (a) nie ma co rozważać, szczególny przypadek (b)), to niby sporo jest mądrych rzeczy w internecie (trzeba oczywiście szukać po angielsku), ale odwołują się one do różnych wymyślnych własności jak np: silniowy system liczbowy itp.. ciekaw jestem, czy da się to jakoś zrobić bardziej elementarnie - tak jak (c)..
jak wypisać te permutacje posortowane w słupku to widać że idąc od prawej do lewej i od \(\displaystyle{ i=0}\) do \(\displaystyle{ i=n-1}\) to liczby się zmieniają co \(\displaystyle{ i!}\), ale wciąż zastanawiam się jak to uporządkować, żeby iść od lewej do prawej i obliczać którą liczbę usunąć z ciągu: \(\displaystyle{ \langle 1,2,...n \rangle}\) i wstawić ją na dane miejsce tworząc szukaną permutację..
co do podpunktu (b) (no bo (a) nie ma co rozważać, szczególny przypadek (b)), to niby sporo jest mądrych rzeczy w internecie (trzeba oczywiście szukać po angielsku), ale odwołują się one do różnych wymyślnych własności jak np: silniowy system liczbowy itp.. ciekaw jestem, czy da się to jakoś zrobić bardziej elementarnie - tak jak (c)..
jak wypisać te permutacje posortowane w słupku to widać że idąc od prawej do lewej i od \(\displaystyle{ i=0}\) do \(\displaystyle{ i=n-1}\) to liczby się zmieniają co \(\displaystyle{ i!}\), ale wciąż zastanawiam się jak to uporządkować, żeby iść od lewej do prawej i obliczać którą liczbę usunąć z ciągu: \(\displaystyle{ \langle 1,2,...n \rangle}\) i wstawić ją na dane miejsce tworząc szukaną permutację..
-
Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
[Algorytmy] Znajdowanie permutacji
(a) i (b) też są proste, idea mniej więcej jak w (c)
Pytamy najpierw jaki jest pierwszy wyraz tej permutacji. Wiadomo, że jak ustale pierwszy wyraz to mam takich permutacji \(\displaystyle{ (n-1)!}\), więc szukam takiego \(\displaystyle{ k}\), żeby:
\(\displaystyle{ m\in [(k-1)\cdot(n-1)!+1;k\cdot (n-1)!]}\). W ten sposób mamy pierwszy wyraz równy \(\displaystyle{ k}\).
Dalej wywołujemy procedurę rekurencyjnie dla zbioru \(\displaystyle{ \{1,2,...,k-1,k+1,..,n\}}\) oraz \(\displaystyle{ m'=m-(k-1)\cdot(n-1)!}\)
Pytamy najpierw jaki jest pierwszy wyraz tej permutacji. Wiadomo, że jak ustale pierwszy wyraz to mam takich permutacji \(\displaystyle{ (n-1)!}\), więc szukam takiego \(\displaystyle{ k}\), żeby:
\(\displaystyle{ m\in [(k-1)\cdot(n-1)!+1;k\cdot (n-1)!]}\). W ten sposób mamy pierwszy wyraz równy \(\displaystyle{ k}\).
Dalej wywołujemy procedurę rekurencyjnie dla zbioru \(\displaystyle{ \{1,2,...,k-1,k+1,..,n\}}\) oraz \(\displaystyle{ m'=m-(k-1)\cdot(n-1)!}\)
-
adambak
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[Algorytmy] Znajdowanie permutacji
uff.. trudniejsze, ale jakoś przyswoiłem.. świetne, wielkie dzięki -- 13 lis 2011, o 14:32 --może komuś się później to jeszcze przyda.. ten wariant ze środkową permutacją jest o tyle fajny, że nie trzeba liczyć silnii, będzie to po prostu ciąg zaczynający się wartością \(\displaystyle{ \left\lfloor \frac{n}{2} \right\rfloor}\) po czym następują wyrazy z tego zbioru, które jeszcze nie wystąpiły w kolejności malejącej.. oczywiście to jest ta "dolna środkowa" permutacja.. jesli chcemy "górną" to analogicznie zaczynać się będzie wartością \(\displaystyle{ \left\lfloor \frac{n}{2} \right\rfloor+1}\) a potem reszta elementów tego zbioru w kolejności rosnącej..