[python-brasil] um exemplo didático de permutações
Rodrigo Dias Arruda Senra
Nossa recente discussão sobre permutações,
me levou a fazer um breve estudo do assunto em
obras da literatura acadêmica .
Quem quiser se aprofundar, eu recomendo [1] (light)
ou [2] (hard-core).
Nossa discussão foi extremamente interessante e agradeço
a todos que partciparam. No entanto, duas coisas
são extremamente frustrantes:
1) Não adianta muito ficar cozinhando o algoritmo mais rápido
para este problema em particular, dada sua natureza NP.
O que significa no popular que para pequenos valores de
N (==cardinalidade do conjunto de elementos a ser permutado)
o tempo de execução cresce absurdamente, tornando-se praticamente
impossível *esperar* pelo resultado.
Quem duvidar basta pegar *qualquer* algoritmo aqui publicado (exceto
Senra2 e Senra3) que estavam errados e testar valores incrementais
de permutações de 3,4,5,... e descubram o limite de sua paciência em assisitr
a CPU fritando ;o)
Isso já é sabido a muito tempo, prova disso no paper [1]:
"""
In short, the fastest possible permuta-
tion method is of limited importance in
practice. There is nearly always a better
way to proceed, and if there is not, the
problem becomes really hopeless when N
is increased only a little.
"""
2) A segunda frustração foram os algoritmos Senra2/Senra3 que são
tentativas *frustradas* de implementar a mesma idéia: Criar um algoritmo
não-recursivo, que preenche as permutações em uma matrix pré-alocada
de dimesão n! x n, de forma que nunca seja necessário testar nenhuma
posição da matrix, apenas fazer atribuições.
O algoritmo Senra2/Senra3 resolvia metade do problema, usava as diagonais
da matriz para realizar o preenchimento. Porém, havia um erro detectado pelo JS,
que consistia na duplicação do cálculo de algumas permutações.
A *boa notícia* é que eu resolvi este problema para o caso de permutações de 3-elementos!
Bastava usar a parte inferior da matriz espelhada, e cada semi-matriz (quadrada) modularmente
cíclica através das diagonais top_right->bottom_left (sentido do percurso).
(1a) (2a) (3a) passada
_ _ 1 2 _ 1 2 3 1
_ 1 _ _ 1 2 3 1 2
1 _ _ 1 2 _ 1 2 3
======================== (espelho)
1 _ _ 1 _ 2 1 3 2
_ 1 _ 2 1 _ 2 1 3
_ _ 1 _ 2 1 3 2 1
A *má notícia* é que eu _não tive saco_ para generalizar para N>3.
Logo se alguém se animar, a idéia é que a cada (n!/n) deve haver uma
troca do elemento escolhido para a diagonal principal, ou diagonal principal
inversa.
Discutindo com um colega de faculdade (Rodrigo Macedo), surgiram algumas
idéias interessantes sobre a relação entre permutações e hipercubos, mas
isto fica para outra thread, outro dia.
Outras atividades vão demandar minha atenção agora, e terei que
abandonar temporariamente este problema. Mas se alguém fizer progresso,
gostaria muito de saber.
Abração,
Senra
[1] Permutation Generation Methods* - ROBERT SEDGEWlCK
1977, Association for Computing Machinery (ref. completa -> Google)
[2] http://www-cs-faculty.stanford.edu/~knuth/taocp.html
Donald Knuth
,_
| ) Rodrigo Senra <rsenra |at| acm.org>
|(______ -----------------------------------------------
_( (|__|] GPr Sistemas http://www.gpr.com.br
_ | (|___|] Blog http://rodsenra.blogspot.com
___ (|__|] IC - Unicamp http://www.ic.unicamp.br/~921234
L___(|_|] -----------------------------------------------
--
,_
| ) Rodrigo Senra <rsenra |at| acm.org>
|(______ -----------------------------------------------
_( (|__|] GPr Sistemas http://www.gpr.com.br
_ | (|___|] Blog http://rodsenra.blogspot.com
___ (|__|] IC - Unicamp http://www.ic.unicamp.br/~921234
L___(|_|] -----------------------------------------------
===============================================================
Antes de enviar sua mensagem dê uma lida em:
http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar
===============================================================
Links do Yahoo! Grupos
<*> Para visitar o site do seu grupo na web, acesse:
http://br.groups.yahoo.com/group/python-brasil/
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@yahoogrupos.com.br
<*> O uso que você faz do Yahoo! Grupos está sujeito aos:
http://br.yahoo.com/info/utos.html
Rodrigo Dias Arruda Senra
[ Gilberto Ximenes <daigor...@yahoo.com.br> ]
-----------------------------------------------
| Mestre Senra,
Onegai Shimasu Daigoro-san!
| sei que peguei a galinha pulando e o bonde andando mas
| este algoritmo não geraria as permutações desejadas ?
Infelizmente não, como já observou outro colega,
mas vamos ao porquê.
| def permuta(lista):
| parada = lista[:]
| while True:
| for x in range(len(lista)-1):
| lista[x], lista[x+1] = lista[x+1], lista[x]
| yield lista
| if parada == lista:
| return
Me parece que vc se inspirou no algoritmo BubbleSort.
O espírito seria ir flutuando os números (através de troca
de elementos adjacentes) do início do vetor ao fim
do vetor, gerando as diversas permutações.
Essa idéia funciona para 3 números pois fixado o primeiro,
uma troca dos remanescentes representa todas as combinações
possíveis.
[3, 2, 1]
[3, 1, 2]
3 fixo, swap(1,2) gera todas as combinações possíveis.
Para qualquer n>3 o método bubble (de 1 passo) vai falhar:
[3, 2, 4, 1] swap(2,4)
[3, 4, 2, 1] swap(2,1)
[3, 4, 1, 2]
Observe que o 1 nunca ficou na frente do 4.
Ordenação é quase um sub-caso de Permutação. Se algum algoritmo *mágico*
lhe desse todas as permutações de um conjunto, bastaria *verificar* qual
delas é que está ordenada (segundo algum critério, por exemplo ordenação
total ascendente).
Logo calculando todas permutações é certamente possível usar isso em
algoritmos de ordenação. Mas *não é preciso* calcular todas as permutações
para se obter ordenação.
E mais do que isso, não é recomendado ! O problema da ordenação baseada em
comparação é Omega(n * log n) e Omega(n) /* quando não está baseado em comparação */
Já o problema de geração das permutações é exponencial!
Mas foi bom vc ter compartilhado suas idéias conosco.
Como diz o ditado: só se chega a perfeição através de muitos erros ;o)
Abração,
Senra