Interessantes Problem beim Sortieren

14

Gegeben eine Röhre mit nummerierten Kugeln (zufällig). Das Rohr hat Löcher, um eine Kugel zu entfernen. Betrachten Sie die folgenden Schritte für eine Operation:

  1. Sie können einen oder mehrere Bälle aus den Löchern auswählen und sich an die Reihenfolge erinnern, in der Sie die Bälle ausgewählt haben.
  2. Sie müssen das Rohr nach links neigen, damit sich die verbleibenden Kugeln im Rohr nach links verschieben und den leeren Raum einnehmen, der durch das Entfernen der Kugeln entsteht.
  3. Sie dürfen die Reihenfolge, in der Sie die nummerierten Kugeln aus der Pfeife genommen haben, nicht ändern. Jetzt steckst du sie wieder in die Pfeife und nutzt den durch die Bewegung der Kugeln entstandenen freien Raum.

Die Schritte 1 bis 3 werden als eine Operation betrachtet.

Finden Sie die minimalen Operationen heraus, die erforderlich sind, um die nummerierten Kugeln in aufsteigender Reihenfolge zu sortieren.

Zum Beispiel: Wenn Tube enthält:[ 1 4 2 3 5 6][1 4 2 3 5 6]

Dann können wir und und , und wenn wir das Rohr nach links neigen, erhalten wir , und wir fügen in dieser Reihenfolge bis zum Ende des Rohrs ein, um zu erhalten .4 5 6 [ 1 2 3 ] ( 4 5 6 ) [ 1 2 3 4 5 6 ]456  [1 2 3]  (4 5 6)     [1 2 3 4 5 6]

Es sind also mindestens 1 Schritte erforderlich. Zum Sortieren der Leitung muss ein Minimum an Arbeitsschritten gefunden werden.

Irgendwelche Ideen oder Hinweise zur Lösung dieses Problems?

Rakesh
quelle
Wenn sie in umgekehrter Reihenfolge auftreten, müssen Sie 2, 3, ... der Reihe nach herausnehmen und am Ende für insgesamt Operationen hinzufügen . Dies ist eindeutig der schlimmste Fall. nn
Vonbrand
2
8,7,6,5,4,3,2,1 -> 75318642 -> 51627384 -> 12345678, indem Sie immer ungerade Positionen herausnehmen.
AdrianN
Zusammenfassend meine Antwort: Die minimale Anzahl von Operationen, die erforderlich sind, um eine Permutation π zu sortieren, ist log 2 ( d ( π - 1 ) + 1 ) , wobei d ( ) die Anzahl der Abfahrten ist. πlog2(d(π1)+1)d()
Yuval Filmus
Ich denke gerne daran, wie man Inversionen entfernt. Mit jeder Operation können Sie Inversionen zwischen jeder Menge X und S - X entfernen (wobei S die gesamte Menge von Kugeln ist). Sie müssen Ihre Sets X also nur sorgfältig auswählen . XSXSX
Joe

Antworten:

10

Definieren die Laufpartitionsnummer einer Permutation π , bezeichnet mit R ( π ) , unter Verwendung des folgenden Prozesses. Sei k die maximale ganze Zahl, so dass die Zahlen min ( π ) , , k in aufsteigender Reihenfolge in π erscheinen . Entfernen Sie sie von π und wiederholen Sie den Vorgang. Die Anzahl der Runden, die benötigt werden, um die gesamte Permutation zu verbrauchen, ist r ( π ) .πr(π)kmin(π),,kππr(π)

Berechnen wir beispielsweise r ( 62735814 ) . Wir legen zuerst 1 beiseite , um 6273584 zu erhalten . Dann legen wir 234 beiseite , um 6758 zu bekommen . Dann legen wir 5 beiseite , um 678 zu bekommen . Schließlich legen wir 678 beiseite , um die leere Permutation zu erhalten. Dies dauert vier Runden, also ist r ( 62735814 ) = 4 .r(62735814)1627358423467585678678r(62735814)=4

Wie ist diese Darstellung zum Sortieren von 62735814 nützlich ? Nehmen Sie jeden zweiten Lauf, dh 234 , 678 , und verschieben Sie diese Zahlen nach rechts, um 51627384 zu erhalten (bearbeiten: in der Reihenfolge, in der sie in der Permutation erscheinen, dh 627384 ). Jetzt gibt es nur zwei Läufe, nämlich 1234 , 5678 , und wir können die Liste sortieren, indem wir 5678 nach rechts verschieben.62735814234,678516273846273841234,56785678

Lassen Sie mich nun die folgende Vermutung machen: Für eine Permutation π sei Π die Menge aller Permutationen, die von π aus in einem Zug erreichbar sind . Dann ist min α Π r ( α ) = r ( π ) / 2 .πΠπminαΠr(α)=r(π)/2

Angesichts dieser Vermutung ist es einfach zu zeigen, dass die minimale Anzahl von Zügen, die zum Sortieren einer Permutation π erforderlich sind, log 2 r ( π ) ⌉ beträgt , und ich habe diese Formel für alle Permutationen in S n für n 8 verifiziert .πlog2r(π)Snn8

Edit: Hier ist eine andere Interpretation der Laufpartitionsnummer , die sie zur Berechnung eines linearen Algorithmus gibt, und ermöglicht es mir , einen Beweis meiner Vermutung zu skizzieren, so dass die Formel Verifizieren log 2 r ( π ) .log2r(π)

Betrachten Sie noch einmal die Permutation 62735814 . Der Grund, warum der erste Lauf mit 1 endet, ist, dass 2 vor 1 erscheint . In ähnlicher Weise endet der zweite Lauf mit 4, da 5 vor 4 erscheint und so weiter. Daher ist die Laufpartitionsnummer einer Permutation die Nummer von i s, so dass i + 1 vor i erscheint .62735814121454ii+1i

Wir können dies prägnanter formulieren, wenn wir die Umkehrung der Permutation betrachten. Betrachte noch einmal π = 62735814 . Nehmen Sie π - 1 = 72485136 . Diese Permutation hat drei Abfahrten: 7 2 48 5 1 36 (eine Abfahrt ist eine Position kleiner als die vorhergehende). Jede Abfahrt entspricht dem Start einer neuen Abfahrt. Also ist r ( π ) gleich eins plus die Anzahl der Abfahrten in π - 1 .π=62735814π1=7248513672485136r(π)π1

Wie sieht die Operation in Bezug auf π - 1 aus ? Sei B die Menge der Zahlen, die wir nach rechts bewegen, und A die Menge der Zahlen, die links bleiben. Wir ersetzen die Zahlen in A durch eine Permutation auf { 1 , , | A | }, die ihre relative Reihenfolge darstellen, und ersetzen Sie die Zahlen in B durch eine Permutation auf { | A | + 1 , , | A | + | B | }π1BAA{1,,|A|}B{|A|+1,,|A|+|B|}. Betrachten Sie zum Beispiel den Zug 6273 5 8 1 451 627384 . In Bezug auf die inversen Permutationen sind es 7 248 5 1362 468 1 357 . So wurden 75 auf 21 und 248136 auf 468357 abgebildet .627358145162738472485136246813577521248136468357

Ein Abstieg ... x y ... in π - 1 , wenn erst nach der Operation verloren x A und y B . Umgekehrt ist in Bezug auf die π - 1 , die Trennwand in A und B entspricht A -Läuft und B -Läuft; Jedes Mal, wenn ein B- Lauf endet und ein A- Lauf beginnt, gibt es eine Abfahrt. Um einen Abstieg zu "töten", müssen wir von einem A- Run zu einem B wechselnxyπ1xAyBπ1ABABBAAB-Lauf. Wenn wir zwei Abfahrten töten, werden wir in der Mitte von einer B- Abfahrt zu einer A- Abfahrt gewechselt sein und eine Abfahrt erleiden.BA

Dieses Argument kann formalisiert werden, um zu zeigen , wenn α von entsteht π über eine Operation, dann d ( α - 1 ) d ( π - 1 ) / 2 , wobei d ( ) ist die Anzahl der Abfahrten. Dies ist äquivalent zu r ( α ) r ( π ) / 2 απd(α1)d(π1)/2d()r(α)r(π)/2, thus proving one direction of my conjecture. The other direction is easier, and was already outlined above: we simply take every second run and push these runs to the right to get a permutation αα satisfying r(α)=r(π/2)r(α)=r(π/2).

Yuval Filmus
quelle
You are taking out several rounds of balls at once, I understand that isn't allowed.
vonbrand
1
I'm taking them in the order they appear in the permutation. That is legal.
Yuval Filmus
i am bit confused. can you please explain min number of operations required to sort [6 5 4 3 2 1] and also you mentioned like "Take every second run, i.e. 234,678, and move these numbers to the right to get 51627384" can you please explian this with detail and also how to calculate r(π) efficently?
user6709
1) r(654321)=6r(654321)=6, so you would need 3 operations. For example, 654321531|64251|62341234|56654321531|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