Quinta, 05 Julho 2018 17:05

ANTONIO CLAUDIO LAGE BUFFARA RESPONDE: QUESTÕES PUC-RIO PERMUTAÇÕES COM PILHAS

Escrito por

Hoje a resolução será de um problema recebido na lista PUC-RIO onde utilizaremos o método de permutação para encontrar o resultado.

PROBLEMA:

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 das 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 permutações possíveis.

Pergunto mais genericamente agora...se eu tivesse os inteiros 1,2...n lidos nesta ordem, quantas das n permutações de 1,2,3...n podem ser obtidas na saída 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).

SOLUÇÃO:

Para clarificar: dada uma permutação fixa "p" de {1,2,...,n}, digamos:

1 -> p(1), 2 -> p(2), ..., n -> p(n)

você tem que empilhar 1, 2, ..., n nessa ordem e desempilhar estes números na ordem p(1), p(2), ..., p(n).

O problema é determinar todas as p (ou pelo menos quantas delas) para as quais isso é possível.

De bate pronto, eu diria que uma condição necessária para p ser realizável é:

p(k) - p(k+1) <= 1, para k = 1, 2, ..., n-1.

Por exemplo, se:

p(1) = 3 e p(2) = 1, a sequência será (E(x) = empilha x;

D(x) = desempilha x):

E(1), E(2), E(3), D(3) e travamos, pois antes de D(1) seremos obrigados a D(2).

Confira a discussão completa em: http://www.mat.puc-rio.br/~obmlistas/obm-l.200312/msg00029.html

Ler 62 vezes Última modificação em Quinta, 05 Julho 2018 17:18

Deixe um comentário

Certifique-se de preencher os campos indicados com (*). Não é permitido código HTML.