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

[Fabio Dias Moreira <fabio.dias.moreira@xxxxxxxxxxxx>]

On 12/02/03 19:17:46, niski 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 ?
> [...]

Uma resposta final está definida unicamente por uma seqüência de 2n  
caracteres, n E e n D, que equivalem às operações Empilhar e  
Desempilhar. É obvio, a pilha secundária nunca pode ser desempilhada  
quando está vazia, logo temos que remover estas possibilidades.

Represente graficamente o processo -- em um instante qualquer, após i  
operações, plote o ponto (i, e-d), onde e é o número de Es que já foram  
executados e d o número de Ds. Termine conectando pontos adjacentes.  
Queremos saber o número de gráficos que tem todas as coordenadas y  
positivas, i.e. que não tocam a reta (x, -1).

Este problema é um problema clássico de combinatória, e sua resposta  
vale 1/n C(2n;n-1). Vale a pena tentar demosntrar isso sozinho.

Você tem certeza de que são só 10?

 1. EDEDEDED
 2. EDEDEEDD
 3. EDEEDEDD
 4. EDEEDDED
 5. EDEEEDDD
 6. EEDEDEDD
 7. EEDEDDED
 8. EEDEEDDD
 9. EEDDEDED
10. EEDDEEDD
11. EEEDEDDD
12. EEEDDEDD
13. EEEDDDED
14. EEEEDDDD

Eu conto 14, que é justamente o que a resposta prevê.

[]s,

-- 
Fábio "ctg \pi" Dias Moreira
GPG key ID: 6A539016BBF3190A (available at wwwkeys.pgp.net)

PGP signature