[obm-l] Permutaçoes com pilhas.

[niski <fabio@xxxxxxxxx>]

Em uma aula de computação me deparei com o seguinte problema :

"Suponha que os inteiros 1, 2, 3 e 4 são lidos nesta ordem. Considerando 
todas as possíveis seqüências de operações de empilhar e desempilhar, 
decida quais da 4! (=24) permutações de 1,2,3,4 podem ser obtidas na 
saída de uma pilha. Por exemplo, a permutação 2,3,1,4 pode ser obtida da 
seguinte forma: empilha 1, empilha 2, desempilha 2, empilha 3, 
desempilha 3, desempilha 1, empilha 4, desempilha 4. "

Fiz na força bruta. Me parece que são 10 permutacoes possiveis.

Pergunto mais genericamente agora...se eu tivesse os inteiros 1,2...n 
lidos nesta ordem, QUANTAS das n! permutacoes de 1,2,3...n podem ser 
obtidas na saida de uma pilha ?

* Definição de pilha :
Uma pilha é uma estrutura de dados que admite remoção de elementos e 
inserção de novos elementos.  Mais especificamente, uma  pilha (= stack) 
  é uma estrutura sujeita à seguinte regra de operação: sempre que 
houver uma remoção, o elemento removido é o que está na estrutura há 
menos tempo.

Em outras palavras, o primeiro objeto a ser inserido na pilha é o último 
a ser removido. Essa política é conhecida pela sigla LIFO (= 
Last-In-First-Out).

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================