Ciekawy problem z sortowaniem

Biorąc pod uwagę tubę z ponumerowanymi kulkami (losowa). Rurka ma otwory do usuwania kulki. Rozważ następujące kroki dla jednej operacji:

1. Możesz wybrać jedną lub więcej piłek z dołków i zapamiętać kolejność, w jakiej je wybrałeś.
2. Musisz przechylić rurę w lewą stronę, aby pozostałe kulki w rurze przesunęły się w lewo i zajmowały puste miejsce utworzone przez usunięcie kul.
3. Nie należy zmieniać kolejności wybierania ponumerowanych piłek z rury. Teraz wkładasz je z powrotem do rury, wykorzystując wolne miejsce utworzone przez ruch kulek.

Kroki od 1 do 3 są uważane za jedną operację.

Dowiedz się, jakie są minimalne operacje wymagane do posortowania ponumerowanych piłek w porządku rosnącym.

Na przykład: Jeśli rura zawiera: $[1\ 4\ 2\ 3\ 5\ 6]$

Następnie możemy wyjąć 4 i 5 i 6 , a jeśli przechylimy rurę w lewo, otrzymamy [ 1 2 3 ] i wstawimy ( 4 5 6 ) w tej kolejności na koniec rury, aby uzyskać [ 1 2 3 4 5 6 ] .$4$$5$$6$$[1\ 2\ 3]$$(4\ 5\ 6)$$[1\ 2\ 3\ 4\ 5\ 6]$

Zatem minimalna wymagana liczba kroków to 1. Muszę znaleźć minimalną liczbę operacji, aby posortować potok.

Wszelkie pomysły lub wskazówki dotyczące rozwiązania tego problemu?

Zdefiniuj numer partycji uruchamiania permutacji π , oznaczony r ( π ) , stosując następujący proces. Niech k będzie maksymalną liczbą całkowitą taką, że liczby min ( π ) , … , k pojawiają się w kolejności rosnącej w π . Usuń je z π i powtórz proces. Liczba rund potrzebnych do pochłonięcia całej permutacji wynosi r ( π ) .$\pi$$r(\pi)$$k$$\min(\pi),\ldots,k$$\pi$$\pi$$r(\pi)$

Na przykład obliczmy r ( 62735814 ) . Najpierw odłożyliśmy 1 , aby uzyskać 6273584 . Następnie odkładamy na bok 234 , aby uzyskać 6758 . Następnie odkładamy na bok 5 , aby uzyskać 678 . Wreszcie odłożyliśmy na bok 678, aby uzyskać pustą permutację. Zajmuje to cztery rundy, więc r ( 62735814 ) = 4 .$r(62735814)$$1$$6273584$$234$$6758$$5$$678$$678$$r(62735814) = 4$

W jaki sposób ta reprezentacja jest przydatna do sortowania 62735814 ? Weź co drugi bieg, tj. 234 , 678 , i przesuń te liczby w prawo, aby uzyskać 51627384 (edytuj: w kolejności, w jakiej pojawiają się w permutacji, tj. 627384 ). Teraz są tylko dwa przebiegi, a mianowicie 1234 , 5678 , i możemy posortować listę, przesuwając 5678 w prawo.$62735814$$234,678$$51627384$$627384$$1234,5678$$5678$

Pozwólcie, że stworzę następującą hipotezę: dla permutacji π niech Π będzie zbiorem wszystkich permutacji, które są osiągalne z π w ramach jednego ruchu. Następnie min α ∈ Π r ( α ) = ⌈ r ( π ) / 2 ⌉ .$\pi$$\Pi$$\pi$$\min_{\alpha \in \Pi} r(\alpha) = \lceil r(\pi)/2 \rceil$

Biorąc pod uwagę tę hipotezę, łatwo jest wykazać, że minimalna liczba ruchów potrzebnych do posortowania permutacji π wynosi ⌈ log 2 r ( π ) ⌉ , i zweryfikowałem tę formułę dla wszystkich permutacji w S n dla n ≤ 8 .$\pi$$\lceil \log_2 r(\pi) \rceil$$S_n$$n \leq 8$

Edycja: Oto inna interpretacja numeru partycji uruchomieniowej, która daje algorytm liniowego czasu do jej obliczenia i pozwala mi naszkicować dowód mojej przypuszczenia, weryfikując w ten sposób wzór ⌈ log 2 r ( π ) ⌉ .$\lceil \log_2 r(\pi) \rceil$

Ponownie rozważ permutację 62735814 . Powodem, dla którego pierwsze uruchomienie kończy się na 1, jest to, że 2 pojawia się przed 1 . Podobnie, drugi cykl kończy się na 4, ponieważ 5 pojawia się przed 4 i tak dalej. Dlatego numer partycji uruchamiania permutacji jest liczbą i, tak że i + 1 pojawia się przed i .$62735814$$1$$2$$1$$4$$5$$4$$i$$i+1$$i$

Możemy powiedzieć to bardziej zwięźle, jeśli spojrzymy na odwrotność permutacji. Zastanów się ponownie π = 62735814 . Weź π - 1 = 72485136 . Ta permutacja ma trzy zjazdy: 7 2 48 5 1 36 (zejście jest pozycją mniejszą niż poprzednia). Każdy zjazd odpowiada początkowi nowego biegu. Więc r ( π ) jest równe jeden plus liczba zejść w π - 1 .$\pi = 62735814$$\pi^{-1} = 72485136$$7\mathbf{2}48\mathbf{5}\mathbf{1}36$$r(\pi)$$\pi^{-1}$

Jak wygląda operacja w kategoriach π - 1 ? niech B będzie zbiorem liczb, które przesuwamy w prawo, a A będzie zbiorem liczb, które pozostają po lewej stronie. Zastępujemy liczby w A permutacją { 1 , … , | A | } reprezentujące ich względną kolejność i zamień liczby w B na permutację na { | A | + 1 , … , | A | + | B | $\pi^{-1}$$B$$A$$A$$\{1,\ldots,|A|\}$$B$$\{|A|+1,\ldots,|A|+|B|\}$. Rozważmy na przykład ruch 6273 5 8 1 4 ↦ 51 627384 . Pod względem odwrotnych permutacji jest to 7 248 5 136 ↦ 2 468 1 357 . Więc 75 zostało zmapowane na 21, a 248136 zmapowane na 468357 .$\mathbf{6273}5\mathbf{8}1\mathbf{4} \mapsto 51\mathbf{627384}$$7\mathbf{248}5\mathbf{136} \mapsto 2\mathbf{468}1\mathbf{357}$$75$$21$$248136$$468357$

Zejście ... x y ... w Õ - 1 jest tracona po operacji tylko wtedy, gdy x ∈ A oraz y ∈ B . I odwrotnie, w kategoriach π - 1 , podział na A i B odpowiada biegom A i biegom B ; za każdym razem, gdy kończy się bieg B i rozpoczyna się bieg A , następuje zejście. Aby „zabić” zejście, musimy zmienić bieg z A na $\ldots xy \ldots$$\pi^{-1}$$x \in A$$y \in B$$\pi^{-1}$$A$$B$$A$$B$$B$$A$$A$$B$-biegać. Jeśli zabijemy dwa zjazdy, zmienimy środek z biegu B na bieg A , powodując zejście.$B$$A$

Argument ten można sformalizować, aby wykazać, że jeśli α powstaje z π przez operację, to d ( α - 1 ) ≥ ⌊ d ( π - 1 ) / 2 ⌋ , gdzie d ( ⋅ ) jest liczbą zejść. Jest to równoważne z r ( α ) ≥ ⌈ r ( π ) / 2 $\alpha$$\pi$$d(\alpha^{-1}) \geq \lfloor d(\pi^{-1})/2 \rfloor$$d(\cdot)$$r(\alpha) \geq \lceil r(\pi)/2 \rceil$, dowodząc w ten sposób jednego kierunku mojej przypuszczenia. Drugi kierunek jest łatwiejszy i został już nakreślony powyżej: po prostu bierzemy co drugi przebieg i popychamy te przebiegi w prawo, aby uzyskać permutację α spełniającą wartość r ( α ) = ⌈ r ( π / 2 ) ⌉ .$\alpha$$r(\alpha) = \lceil r(\pi/2) \rceil$