[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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



> Oi, Niski:
> 
> Soh pra clarificar: dada uma permutacao fixa "p" de {1,2,...,n}, digamos:
> 1 -> p(1), 2 -> p(2), ..., n -> p(n),

Não entendi muito bem sua notação.
p(1) entende-se por "posição 1"?

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

Eu estava dando o seguinte tratamento (p/ n = 4)

Para gerar uma permutacao de 4 elementos, necessito de 8 operacoes.

E1 D1 E2 E3 D3 D2 E4 D4 -> gera 1 3 2 4

Essa mesma sequencia pode ser gerada de outra forma?
Qualquer outra sequencia pode ser gerada de outra forma?

Será que existe alguma relação que deve ser obedecida entre as 
"distancias" das operacoes E(x) e D(x) ?


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