Biorąc pod uwagę tubę z ponumerowanymi kulkami (losowa). Rurka ma otwory do usuwania kulki. Rozważ następujące kroki dla jednej operacji:
- Możesz wybrać jedną lub więcej piłek z dołków i zapamiętać kolejność, w jakiej je wybrałeś.
- 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.
- 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 ] .
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?
sorting
permutations
rakesh
źródło
źródło
Odpowiedzi:
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 ( π ) .π r(π) k min(π),…,k π π r(π)
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 ⌉ .π Π π minα∈Πr(α)=⌈r(π)/2⌉
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 .π ⌈log2r(π)⌉ Sn n≤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 ( π ) ⌉ .⌈log2r(π)⌉
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 .π=62735814 π−1=72485136 72485136 r(π) π−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 | }π−1 B A A {1,…,|A|} B {|A|+1,…,|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 .62735814↦51627384 72485136↦24681357 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 B…xy… π−1 x∈A y∈B π−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 ⌉α π d(α−1)≥⌊d(π−1)/2⌋ d(⋅) r(α)≥⌈r(π)/2⌉ , 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 ) ⌉ .α r(α)=⌈r(π/2)⌉
źródło