Rozważam taki problem: mamy dowolną permutację zbioru \(\displaystyle{ Z=\left\{ 1,2,3,..,n\right\}}\). Teraz złożymy ją z ją samą. Następnie permutację, którą otrzymamy, składamy z daną na początku, i tak w kółko. Zauważyłem, że po pewnym czasie wyniki zaczynają się powtarzać (niestety nie umiem tego udowodnić). Pytanie brzmi: czy mając daną liczbę \(\displaystyle{ n}\) możemy policzyć po ilu złożeniach, w najgorszym wypadku, wyniki zaczną się powtarzać? Dajmy taki przykład:
permutacja: \(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right)}\)
i oto co robimy:
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 7 & 5 & 6\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 7 & 5 & 6\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 5 & 6 & 7\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 5 & 6 & 7\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 6 & 7 & 5\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 6 & 7 & 5\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 7 & 5 & 6\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 7 & 5 & 6\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7\end{array}\right)}\)
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7\end{array}\right) \ \circ \ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right) = \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 2 & 1 & 6 & 7 & 5\end{array}\right)}\)
czy wszystko jest poprawne pod względem zapisu? od tej chwili wyniki zaczynają się powtarzać. Główny problem to wyznaczanie liczby na \(\displaystyle{ i}\)-tym miejscu w permutacji po \(\displaystyle{ k}\)-tym jej złożeniu tak jak w przykładzie, ale najpierw chciałem się skupić nad tym czy jest możliwe oszacowanie po ilu złożeniach, w najgorszym przypadku, wyniki zaczną się powtarzać, mając dane \(\displaystyle{ n}\). Być może niepotrzebnie, łatwiej jest rozwiązać od razu główny problem? Bo rozumiem, że jeśli na wejściu by była inna permutacja (z tym samym \(\displaystyle{ n}\)) to wyniki mogłyby zacząć się powtarzać po innej liczbie złożeń..
Jakieś wskazówki co do składania permutacji?
Składanie permutacji - powtarzalność
-
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
Składanie permutacji - powtarzalność
To jest zadanie z teorii grup. W szczególnym przypadku gdy mamy do czynienia z permutacjami wystarczy znaleźć rozkład na cykle rozłączne (polecam googlować to hasło) i policzyć NWW z długości tych cykli. Wynikiem tej operacji będzie minimalna liczba złożeń potrzebna aby otrzymać permutację identycznościową, po kolejnym domnożeniu otrzymamy oczywiście permutację wejściową.
Aha, a jeśli chcesz liczyć szybko k-tą potęgę tej permutacji to robi się to tak, ze rozkładasz na cykle rozłączne i w każdym cyklu robisz przesunięcie o \(\displaystyle{ k \mbox{ mod d}}\) gdzie \(\displaystyle{ d}\) to długość cyklu. Idea stanie się jasna gdy rozważysz np. taki przykład:
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 3 & 1 & 4 & 5 & 6 & 7\end{array}\right)}\)
powiedzmy \(\displaystyle{ k=1001}\)
Po chwili zastanowienia widać, że mamy taki cykl w permutacji \(\displaystyle{ 1 \to 2\to 3 \to 1 \to 2 ...}\), więc zamiast składać \(\displaystyle{ 1000}\) razy wystarczy złożyć \(\displaystyle{ 2}\) razy i na to samo wyjdzie.
Ogólnie każdą permutację da sie przedstawić jako "rozłączny" iloczyn takich cykli.
edit: w szczególności można podnosić permutację do dowolnej (sensownej) potęgi w czasie \(\displaystyle{ O(n)}\)
Aha, a jeśli chcesz liczyć szybko k-tą potęgę tej permutacji to robi się to tak, ze rozkładasz na cykle rozłączne i w każdym cyklu robisz przesunięcie o \(\displaystyle{ k \mbox{ mod d}}\) gdzie \(\displaystyle{ d}\) to długość cyklu. Idea stanie się jasna gdy rozważysz np. taki przykład:
\(\displaystyle{ \left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 3 & 1 & 4 & 5 & 6 & 7\end{array}\right)}\)
powiedzmy \(\displaystyle{ k=1001}\)
Po chwili zastanowienia widać, że mamy taki cykl w permutacji \(\displaystyle{ 1 \to 2\to 3 \to 1 \to 2 ...}\), więc zamiast składać \(\displaystyle{ 1000}\) razy wystarczy złożyć \(\displaystyle{ 2}\) razy i na to samo wyjdzie.
Ogólnie każdą permutację da sie przedstawić jako "rozłączny" iloczyn takich cykli.
edit: w szczególności można podnosić permutację do dowolnej (sensownej) potęgi w czasie \(\displaystyle{ O(n)}\)