Comment détecter l'ordre des piles?

Nous prenons la séquence d'entiers de à , et nous les poussons dans une pile un par un dans l'ordre. Entre chaque poussée, nous pouvons choisir de faire apparaître n'importe quel nombre d'éléments de la pile (de 0 à la taille de pile actuelle).$1$$n$

Chaque fois que nous sortons une valeur de la pile, nous l'imprimons.

Par exemple, est imprimé lorsque nous le faisons . vient .$1,2,3$push, pop, push, pop, push, pop$3,2,1$push, push, push, pop, pop, pop

Cependant, n'est pas une impression possible, car il n'est pas possible d'avoir imprimés suivis de , sans voir entre les deux.$3,1,2$$3$$1$$2$

Question: Comment pouvons-nous détecter des commandes impossibles comme ?$3,1,2$

En fait, sur la base de mon observation, j'ai trouvé une solution potentielle. Mais le problème est que je ne peux pas prouver que mon observation est complète.

Le programme que j'ai écrit avec la logique suivante:

Lorsque la valeur actuelle moins la valeur suivante est supérieure à 1, une valeur entre le courant et le suivant ne peut pas apparaître après le suivant. Par exemple, si current = 3 et next = 1, alors la valeur entre current (3) et next (1) est 2 qui ne peut pas apparaître après next (1), donc viole la règle.$3,1,2$

Est-ce que cela couvre tous les cas?

Je ne pouvais pas comprendre exactement votre approche (semble correct), mais il existe une règle simple pour les ordres impossibles: l'ordre est impossible il y a tels que et . Pour un tel nous disons mauvais triple.$iff$$a_i,a_j,a_k$$a_i > a_k > a_j$$i<j<k$$a_i,a_j,a_k$

Pourquoi? Vous devez d'abord prouver que s'il y a un mauvais triple, la séquence est impossible, mais c'est simple et je vais le laisser comme exercice (le nombre moyen ne peut pas apparaître plus tôt que le plus grand sauf le plus petit avant tous).

Deuxièmement, vous devez prouver que tous les ordres impossibles ont au moins un mauvais triple. Supposons que vous ayez une séquence sans mauvais triple, vous pouvez trouver l'ordre de push et pop, donc ce n'est pas une séquence impossible. Pour reconstruire les ordres push et pop, utilisez simplement une approche naïve (l'opération est pop pendant que vous itérez sur des nombres consécutifs), mais pour la preuve formelle (pour plus de simplicité) vous pouvez utiliser l'induction, supposez pour toutes les séquences de longueur s'il n'y a pas de mauvais triple ils ne sont pas impossibles. Pour la séquence de longueur , vous pouvez définir des opérations comme pop (début de fin de séquence), tout en rencontrant des nombres consécutifs croissants, vous avez maintenant une séquence de longueur , avec$m$$n$$m$$m < n$, sans mauvais triple, donc vous pouvez reconstruire le push and pop pour cette séquence, donc l'original n'était pas impossible. le début de l'induction est une séquence de longueur 3.