Ciekawy problem z sortowaniem

14

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 ]     [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 ] .456  [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?

rakesh
źródło
Jeśli są w odwrotnej kolejności, musisz wyjąć 2, 3, ... w kolejności i dodać na końcu, dla wszystkich n operacji. To zdecydowanie najgorszy przypadek. n
vonbrand
2
8,7,6,5,4,3,2,1 -> 75318642 -> 51627384 -> 12345678, zawsze usuwając nieparzyste pozycje.
adrianN
Podsumowując moją odpowiedź: minimalna liczba operacji wymaganych do posortowania permutacji π wynosi log 2 ( d ( π - 1 ) + 1 ) , gdzie d ( ) to liczba zejść. πlog2(d(π1)+1)d()
Yuval Filmus
Lubię o tym myśleć w kategoriach usuwania inwersji. Przy każdej operacji możesz usunąć odwrócenie między dowolnym zestawem X i S - X (gdzie S to cały zestaw kulek). Musisz więc ostrożnie wybrać zestawy X. XSXSX
Joe,

Odpowiedzi:

10

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(π)kmin(π),,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)1627358423467585678678r(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.62735814234,678516273846273841234,56785678

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(π)Snn8

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 .62735814121454ii+1i

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=7248513672485136r(π)π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 | }π1BAA{1,,|A|}B{|A|+1,,|A|+|B|}. Rozważmy na przykład ruch 6273 5 8 1 451 627384 . Pod względem odwrotnych permutacji jest to 7 248 5 1362 468 1 357 . Więc 75 zostało zmapowane na 21, a 248136 zmapowane na 468357 .627358145162738472485136246813577521248136468357

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 Bxyπ1xAyBπ1ABABBAAB-biegać. Jeśli zabijemy dwa zjazdy, zmienimy środek z biegu B na bieg A , powodując zejście.BA

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)/2d()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)

Yuval Filmus
źródło
Wyciągasz kilka rund piłek jednocześnie, rozumiem, że to niedozwolone.
vonbrand
1
Biorę je w kolejności, w jakiej pojawiają się w permutacji . To jest legalne.
Yuval Filmus
jestem trochę zmieszany. czy możesz wyjaśnić minimalną liczbę operacji wymaganych do sortowania [6 5 4 3 2 1], a także wspomniałeś: „Weź co drugi bieg, tj. 234 678, i przenieś te liczby w prawo, aby uzyskać 51627384”. Czy możesz to wyjaśnić za pomocą szczegóły, a także jak skutecznie obliczyć r (π)?
user6709
1) r(654321)=6, so you would need 3 operations. For example, 654321531|64251|62341234|56.
Yuval Filmus
2) You take all the numbers belonging to these runs (in the order they appear in the permutation), and move them to the right. In this case, you take 627384 and move them to the right, leaving 51 to the left.
Yuval Filmus