Générer une permutation en utilisant une seule pile

Question

Quelqu'un peut-il expliquer l'algorithme permettant de générer les permutations possibles lorsqu'on utilise une seule pile et que les opérations push et pop sont les seules autorisées. J'ai beaucoup cherché sur ce sujet, mais je n'ai pas trouvé de réponse définitive. De plus, le nombre total de ces permutations est donné par les nombres catalans. Mais je n'ai pas réussi à obtenir de preuve à ce sujet. Merci de m'expliquer cela aussi, si possible.

Merci !

Answer 1

Ce problème utilise une file d'entrée et une file de sortie ainsi qu'une pile.

Les opérations sont "pousser un élément de la file d'entrée sur la pile" et "transférer un élément de la pile sur la file de sortie".

                  1 2 3
output  ______   ______  input  
              \ /
        <--+   |   +---
       pop |   |   | push
           |   |   v

             stack

Par exemple, avec l'entrée 1 2 3 vous pouvez obtenir le résultat suivant 2 1 3 dans l'ordre suivant :

• pousser 1 de l'entrée vers la pile
• pousser 2 de l'entrée vers la pile
• pop 2 de la pile vers la sortie
• pop 1 de la pile vers la sortie
• pousser 3 de l'entrée vers la pile
• pop 3 de la pile vers la sortie

Mais tu auras du mal si tu essaies de générer 3 1 2 .

---

Comment générer toutes les permutations possibles avec ces opérations ? Eh bien, il est trivial de le faire de manière récursive : dans n'importe quel état donné (où l'"état" est constitué du contenu de la file d'attente d'entrée, de la pile et de la file d'attente de sortie), il y a au plus deux opérations possibles que vous pouvez effectuer (vous pouvez pousser s'il y a au moins un élément sur la file d'attente d'entrée ; vous pouvez pousser s'il y a au moins un élément sur la pile), ce qui vous donnera au plus deux nouveaux états possibles à explorer.

Pour plus de détails concernant ce problème, et la relation avec les nombres catalans, allez chercher une copie de "The Art of Computer Programming" de Knuth, volume 1 (3ème édition) - c'est discuté dans le §2.2.1 ; voir les exercices 2 - 5 sur les pages 242-243 (et une meilleure version de mon diagramme sur la page 240 !)

Answer 2

Tout d'abord, il est impossible d'écrire un algorithme qui le fasse pour une permutation arbitraire sous les hypothèses suivantes :

1. Vous ne pouvez lire l'entrée que de manière séquentielle.

2. L'écriture de la sortie se fait de manière séquentielle, et les données écrites sur la sortie ne peuvent pas être lues une fois écrites.

3. En plus de la pile unique, vous ne disposez que d'une quantité constante de mémoire. (Cela signifie qu'il n'y a pas de récursion ou de structures de données supplémentaires).

Ceci est une conséquence du lemme de pompage pour les langages sans contexte :

Wiki : http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages

(Ou aussi vérifier : Michael Sipser (1997). Introduction à la théorie du calcul. Je crois que c'est l'un des exercices du chapitre 4).

Maintenant, vous pouvez facilement implémenter un algorithme qui résout ce problème en brisant l'une de ces hypothèses. Par exemple, si vous pouvez lire l'entrée de façon arbitraire, alors vous n'avez pas besoin de pile :

def permute(seq, permutation):
    result = []
    for i in permutation:
        result.push(seq[i])
    return result

Ou si vous fixez une permutation, le problème devient fini et vous n'avez pas non plus besoin d'une pile. Il suffit de déployer l'algorithme habituel au cas particulier sur toutes les entrées (c'est comme faire une évaluation partielle dans un compilateur). C'est assez horrible, donc je ne vais pas m'embêter à écrire tous les détails, mais cela fonctionne toujours grâce au fait que le nombre total d'entrées possibles est une constante fixe (mais grande !).

Answer 3

Je pensais au même problème et j'ai fini par écrire un petit programme Prolog pour générer les permutations, et j'ai "découvert" la relation avec les nombres catalans, puis j'ai trouvé votre question. Ce n'est donc pas vraiment une réponse à votre question mais voici le programme Prolog :

% Generate permutation counts
count_pushpop(N-K) :-
    length(_, N),
    findall(Seq, pushpop(N, Seq), Seqs),
    length(Seqs, K).

% Create an integer sequence from 1 to N
% and permutate it using all possible push-pop
% operations starting with an empty stack.
pushpop(N, Seq) :-
    numlist(1, N, List),
    pushpop(List, [], Seq).

% Generate all the possible ways a list
% of items can be pushed into a stack
% and poped out of it.
pushpop([], [], []).

pushpop([H | List], Stack, Seq) :-
    pushpop(List, [H | Stack], Seq).

pushpop(List, [H | Stack], [H | Seq]) :-
    pushpop(List, Stack, Seq).

Preuve que tous les n! permutations sont possibles :

?- findall(Seq, pushpop(3, Seq), Seqs).
Seqs = [[3, 2, 1], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3]].

Preuve qu'il génère des nombres catalans (ou ce serait être une preuve si ce n'était pas pour le débordement de la pile ;)) :

?- count_pushpop(N-K).
N = K, K = 0 ;
N = K, K = 1 ;
N = K, K = 2 ;
N = 3,
K = 5 ;
N = 4,
K = 14 ;
N = 5,
K = 42 ;
N = 6,
K = 132 ;
N = 7,
K = 429 ;
N = 8,
K = 1430 ;
N = 9,
K = 4862 ;
N = 10,
K = 16796 ;
N = 11,
K = 58786 ;
N = 12,
K = 208012 ;
ERROR: Out of global stack