Re: [obm-l] Permutaçoes com pilhas.

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 02.12.03 19:17, niski at fabio@niski.com wrote:

> 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).
> 
Oi, Niski:

Soh pra clarificar: dada uma permutacao fixa "p" de {1,2,...,n}, digamos:
1 -> p(1), 2 -> p(2), ..., n -> p(n),
voce tem que empilhar 1, 2, ..., n nessa ordem e desempilhar estes numeros
na ordem p(1), p(2), ..., p(n).

O problema eh determinar todas as p (ou pelo menos quantas delas) para as
quais isso eh possivel.

De bate pronto, eu diria que uma condicao necessaria pra p ser realizavel
eh: p(k) - p(k+1) <= 1, para k = 1, 2, ..., n-1.

Por exemplo, se p(1) = 3 e p(2) = 1, a sequencia serah (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).

Serah que essa condicao tambem eh suficiente?

Um abraco,
Claudio.


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