Wie erkenne ich die Stapelreihenfolge?

Wir nehmen die Folge von ganzen Zahlen von bis und schieben sie nacheinander auf einen Stapel. Zwischen jedem Push können wir eine beliebige Anzahl von Elementen aus dem Stapel entfernen (von 0 bis zur aktuellen Stapelgröße).$1$$n$

Jedes Mal, wenn wir einen Wert aus dem Stapel entfernen, drucken wir ihn aus.

Zum Beispiel wird ausgedruckt, wenn wir dies tun . kommt von .3 , 2 , $1,2,3$push, pop, push, pop, push, pop$3,2,1$push, push, push, pop, pop, pop

Jedoch ist nicht möglich , ein Ausdruck, weil es nicht möglich ist, hat durch gefolgt gedruckt , ohne zu sehen dazwischen.3 1 $3,1,2$$3$$1$$2$

Frage: Wie können wir unmögliche Aufträge wie ?$3,1,2$

Aufgrund meiner Beobachtung habe ich tatsächlich eine mögliche Lösung gefunden. Das Problem ist jedoch, dass ich nicht beweisen kann, dass meine Beobachtung vollständig ist.

Das Programm, das ich mit der folgenden Logik geschrieben habe:

Wenn der aktuelle Wert abzüglich des nächsten Werts größer als 1 ist, kann nach dem nächsten Wert kein Wert zwischen aktuell und weiter angezeigt werden. Wenn beispielsweise current = 3 und next = 1 ist, ist der Wert zwischen current (3) und next (1) 2, der nach next (1) nicht . verstößt gegen die Regel.$3,1,2$

Deckt dies alle Fälle ab?

Ich konnte Ihren Ansatz nicht genau verstehen (scheint richtig zu sein), aber es gibt eine einfache Regel für unmögliche Ordnungen: Die Reihenfolge ist unmöglich, es so dass und . Zu solch einem sagen wir schlechtes Dreifach.a i , a j , a k a i > a k > a j i < j < k a i , a j , a $iff$$a_i,a_j,a_k$$a_i > a_k > a_j$$i<j<k$$a_i,a_j,a_k$

Warum? Zuerst sollten Sie beweisen, dass die Sequenz unmöglich ist, wenn es ein schlechtes Triple gibt, aber das ist einfach und ich lasse es als Übung (die mittlere Zahl könnte nicht früher als die größere platzen, außer die kleinere, die vor allen von ihnen platzt).

Zweitens sollten Sie beweisen, dass alle unmöglichen Befehle mindestens ein schlechtes Tripel haben. Angenommen, Sie haben eine Sequenz ohne schlechtes Tripel. Sie könnten die Reihenfolge von Push und Pop finden, so dass es keine unmögliche Sequenz ist. Verwenden Sie für die Rekonstruktion der Push- und Pop-Befehle nur einen naiven Ansatz (die Operation ist Pop, während Sie über aufeinanderfolgende Zahlen iterieren). Für einen formalen Beweis (der Einfachheit halber) können Sie jedoch die Induktion verwenden, für alle Sequenzen der Länge dass es kein schlechtes Tripel gibt Sie sind nicht unmöglich. Für die Sequenz der Länge können Sie Operationen als Pop festlegen (Beginn am Ende der Sequenz), während Sie auf zunehmende aufeinanderfolgende Zahlen stoßen. Jetzt haben Sie eine Sequenz der Länge mitn m m < $m$$n$$m$$m < n$, ohne schlechtes Triple, so dass Sie Push und Pop für diese Sequenz rekonstruieren können, so dass die ursprüngliche nicht unmöglich war. Beginn der Induktion ist die Sequenz der Länge 3.