"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 =========================================================================
