Re: [python-brasil] Um exemplo didático de permutações
Rodrigo Dias Arruda Senra
Antes de dormir resolvi tentar uma outra abordagem para
gerar as permutações. Ainda seguindo a idéia de gerar todas ao mesmo
tempo !
A idéia que eu tive foi alocar espaço para todas as permutações, empilhar estes vetores
e simplesmente ir distribuindo os números pelos espaços alocados, usando as diagonais.
Por exemplo, para gerar as permutações de (1, 2, 3)
sabemos que são 3!==6 permutações cada uma com 3 elementos
Logo aloca-se este espaço:
_ _ _
_ _ _
_ _ _
_ _ _
_ _ _
_ _ _
Daí em diante sei que cada número vai aparecer uma única vez em
cada linha (cada permutação). Logo saio distribuindo o número '1' 6
vezes ao longo da diagonal:
1 _ _
_ 1 _
_ _ 1
1 _ _
_ 1 _
_ _ 1
Mesma coisa para o '2', que segue a mesma diagonal com um
deslocamento (módulo tamanho do vetor):
1 2 _
_ 1 2
2 _ 1
1 2 _
_ 1 2
2 _ 1
Repete para o 3. E pronto!
A implementação dessa idéia em Python é bem simples:
# Usando Python puro
from array import array
def permuta_opt(S):
n = len(S) # tamanho do vetor
# calcula o fatorial
fat = reduce(lambda x,y: x*y, range(1,n+1))
# aloca espaço para os vetores
permutations = []
for i in range(fat):
permutations.append(array('i',[0]*n))
a = 0 # qual array
x = 0 # em que posição no array a
for e in S: # para todos os elementos
for r in xrange(fat): # cada elemento ocorre fatorial vezes
permutations[a][x]=e
a = (a + 1) % fat
x = (x + 1) % n
x = (x + 1) % n # muda de elemento, dá um pulinho pro lado
return permutations
# Mesma idéia usando Numarray
from numarray import array
def permuta_opt2(S):
n = len(S)
fat = reduce(lambda x,y: x*y, range(1,n+1))
permutations = array([0]*n*fat)
permutations.shape = (fat,n)
a, x = 0, 0
for e in S:
for r in xrange(fat):
permutations[a][x]=e
a = (a + 1) % fat
x = (x + 1) % n
x = (x + 1) % n
return permutations
Acho que é uma idéia ainda mais clara e didática do que
o primeiro algoritmo que eu postei! E ainda mais lerdo!!! hehehehe
Niemeyer [0.0013790130615234375, 0.0013720989227294922, 0.0020899772644042969]
Ademir [0.0017268657684326172, 0.0017271041870117188, 0.0017211437225341797]
Senra2 [0.084505081176757812, 0.30484604835510254, 1.7482759952545166]
Não é que a minha implementação seja tão ruim <wink>, mas **suspeito** que a abordagem (algoritmo) de
construir todas permutações ao mesmo tempo (em Python) seja *inerentemente* mais lerda que
construir uma permutação de cada vez. Talvez se codificado em C puro esta versão fosse mais rápida de ser codificada,
pois não exigiria pilha, apenas vetor. Não sei se existe maneira de torná-la tão rápida quanto
a versão do Niemeyer em Python ? Alguém se habilita ?
Bom por hoje eu vou jogar a toalha e vou dormir, pois estou babando de sono, logo boa noite.
Abração
Senra
--
,_
| ) 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
O título deste e-mail deveria ser:
"Senra: A História de uma Anta!!!"
| Antes de dormir resolvi tentar uma outra abordagem para
| gerar as permutações. Ainda seguindo a idéia de gerar todas ao mesmo
| tempo !
Pois é são 03:20 e ainda não consegui dormir. Estava tremendamente frustrado
por não entender o que estava acontecendo.
| Niemeyer [0.0013790130615234375, 0.0013720989227294922, 0.0020899772644042969]
| Ademir [0.0017268657684326172, 0.0017271041870117188, 0.0017211437225341797]
| Senra2 [0.084505081176757812, 0.30484604835510254, 1.7482759952545166]
Uma vez que o problema de calcular as permutações cresce exponencialmente no tamanho da
entrada como que o algoritmo do (do==postado por) Niemeyer e do Ademir aparentavam
ter complexidade O(1). Impossível.
Desliguei tudo e fui tomar banho. Splash! Como dizia Arthur Conan Doyle através de seu
personagem SHerlock Holmes: "Eliminando o impossível, o que sobra é a verdade"
Senra (acrônimo recursivo para: Senra Encarnado Numa Reles Anta) percebeu que só seu
algoritmo não retornava um generator , ou seja, eu estava só chamando a primeira iteração
dos geradores no caso do Niemeyer e do Ademir, e no meu calculava tudo!
Ok, aí refiz as estatísticas, dessa vez corretamente hehehehe. Ou seja todo mundo calculando
todas as permutações e não eu todas e os outros 1.
E daí:
Permutações com 3, 4 e 5 elementos.
Senra0 [0.55031800270080566, 2.3629460334777832, 12.067134857177734] # recursivo c/ conjuntos
Senra1 [0.070784091949462891, 0.27344393730163574, 1.3998148441314697] #
Senra2 [0.10543417930603027, 0.28776812553405762, 1.5710010528564453]
Senra3 [0.52463889122009277, 2.0986988544464111, 12.402277946472168]
Ademir [0.11431193351745605, 0.49631500244140625, 2.7318329811096191]
Niemeyer [0.12308788299560547, 0.62256097793579102, 3.5955190658569336]
O mundo voltou a fazer sentido, pois as curvas assintóticas voltaram para seus devidos lugares.
Explicações a posteriori, pois agora vou dormir meeeeeesmo.
Recomendo que a galera revise estes resultados, depois de eu ter dado essa gafe!
"""
Quando estiver com sono não programe. Melhor faltar na segunda-feira, do que ir programar
com sono, e depois ter que passar o resto da semana depurando o código de segunda-feira
"""
_não sei quem é o autor da frase, mas tenho a forte impressão de que não fui eu_
<code>
# -*- coding: iso-8859-1 -*-
from sets import Set
def permuta(S):
if not S:
return
result = []
for i in S:
S1 = S.difference(Set((i,)))
parcial = permuta(S1)
if not parcial:
result.append((i,))
else:
for j in parcial:
result.append((i,)+j)
return result
def nr_permuta(S):
solucao = [(tuple(),S)] # nenhuma permutação, Todos elementos para permutar
while 1:
parcial = []
for permutacao, faltando in solucao:
for i in faltando:
S1 = faltando - Set((i,))
if permutacao:
parcial.append(((i,)+permutacao,S1))
else:
parcial.append(((i,),S1))
solucao = parcial
#print solucao # para facilitar o entendimento descomente aqui
if not sum([True for i in solucao if i[1]]):
break # todos conjuntos faltantes vazios
return [i[0] for i in solucao]
def nr_permuta_opt(S):
solucao = [(tuple(),S)] # nenhuma permutação, Todos elementos para permutar
while 1:
parcial = []
for permutacao, faltando in solucao:
for i in faltando:
S1 = faltando[:]
S1.remove(i)
if permutacao:
parcial.append(([i]+permutacao,S1))
else:
parcial.append(([i],S1))
solucao = parcial
#print solucao # para facilitar o entendimento descomente aqui
if not solucao[0][1]:
break # todos conjuntos faltantes vazios
return [i[0] for i in solucao]
def permutation(lst):
queue = [-1]
lenlst = len(lst)
while queue:
i = queue[-1]+1
if i == lenlst:
queue.pop()
elif i not in queue:
queue[-1] = i
if len(queue) == lenlst:
yield [lst[j] for j in queue]
queue.append(-1)
else:
queue[-1] = i
def Combine(items, n):
if n == 0:
yield []
else:
for i in xrange(len(items)):
for c in Combine(items[ :i ] + items[ i + 1: ], n-1):
yield [items[ i ]] + c
def Permutations(items):
return Combine(items, len(items))
from array import array
def permuta_opt(S):
n = len(S)
fat = reduce(lambda x,y: x*y, range(1,n+1))
permutations = []
for i in range(fat):
permutations.append(array('i',[0]*n))
a = 0 # array index
x = 0 # position index
for e in S:
for r in xrange(fat):
permutations[a][x]=e
a = (a + 1) % fat
x = (x + 1) % n
x = (x + 1) % n
return permutations
from numarray import array as ar
def permuta_opt2(S):
n = len(S)
fat = reduce(lambda x,y: x*y, range(1,n+1))
permutations = ar([0]*n*fat)
permutations.shape = (fat,n)
a = 0 # array index
x = 0 # position index
for e in S:
for r in xrange(fat):
permutations[a][x]=e
a = (a + 1) % fat
x = (x + 1) % n
x = (x + 1) % n
return permutations
import profile
def Ademir(seed):
return [x for x in Permutations(seed)]
def Niemeyer(seed):
return [x for x in permutation(seed)]
def Senra0(seed):
return permuta(Set(seed))
def Senra1(seed):
return nr_permuta_opt(seed)
def Senra2(seed):
return permuta_opt(seed)
def Senra3(seed):
return permuta_opt2(seed)
def Show(iterable):
for i in iterable:
print i
from timeit import Timer
run = { 'Ademir':[], 'Senra3':[], 'Senra2':[], 'Senra1':[], 'Senra0':[], 'Niemeyer':[]}
perm_sizes = (3,4,5)
for q in perm_sizes:
seed = range(q)
for r,l in run.items():
t = Timer('%s(seed)'%r, 'from __main__ import %s, seed'%r)
try:
l.append(t.timeit(1000))
except:
t.print_exc()
for r,l in run.items():
print r, l
</code>
| Acho que é uma idéia ainda mais clara e didática do que
| o primeiro algoritmo que eu postei! E ainda mais lerdo!!! hehehehe
Não não era mais lerdo não. Ufa!
| Não é que a minha implementação seja tão ruim <wink>, mas **suspeito** que a abordagem (algoritmo) de
| construir todas permutações ao mesmo tempo (em Python) seja *inerentemente* mais lerda que
| construir uma permutação de cada vez.
Não não é! O preço pago no maior consumo de memória deveria ter um retorno
em desempenho de execução... e teve.
|Talvez se codificado em C puro esta versão fosse mais rápida de ser codificada,
| pois não exigiria pilha, apenas vetor. Não sei se existe maneira de torná-la tão rápida quanto
| a versão do Niemeyer em Python ? Alguém se habilita ?
Acho que eu mesmo me habilitei.
| Bom por hoje eu vou jogar a toalha e vou dormir, pois estou babando de sono, logo boa noite.
Agora é para valer!
Boa noite pythoníssima galera.
João Paulo Fernandes Farias
Olha só! Consegui diminuir o tempo...
Pra começo de conversa, o algoritmo NÃO É MEU!!!!
Peguei neste site:
http://www.cs.byuh.edu/~johnsonj/permute/soda_submit.html
E converti pra Python.
PS: Comentei o Senra3 pq num tou com o numarray instalado.
--
JP
$ python permutacoes.py
Senra1 [0.054661989212036133, 0.22546792030334473, 1.1394989490509033]
Senra0 [0.35795903205871582, 1.5582859516143799, 9.547680139541626]
Senra2 [0.054311037063598633, 0.20176506042480469, 1.1581778526306152]
JP [0.0050117969512939453, 0.0055840015411376953, 0.0068459510803222656]
Ademir [0.076399087905883789, 0.33362698554992676, 1.9873781204223633]
Niemeyer [0.098239898681640625, 0.45242905616760254, 2.8897631168365479]
from array import array
def permuta_opt(S):
n = len(S)
fat = reduce(lambda x,y: x*y, range(1,n+1))
permutations = []
for i in range(fat):
permutations.append(array('i',[0]*n))
a = 0 # array index
x = 0 # position index
for e in S:
for r in xrange(fat):
permutations[a][x]=e
a = (a + 1) % fat
x = (x + 1) % n
x = (x + 1) % n
return permutations
#from numarray import array as ar
#def permuta_opt2(S):
# n = len(S)
# fat = reduce(lambda x,y: x*y, range(1,n+1))
# permutations = ar([0]*n*fat)
# permutations.shape = (fat,n)
# a = 0 # array index
# x = 0 # position index
# for e in S:
# for r in xrange(fat):
# permutations[a][x]=e
# a = (a + 1) % fat
# x = (x + 1) % n
# x = (x + 1) % n
# return permutations
#import profile
# implementação em python da versão em C encontrada em:
# http://www.cs.byuh.edu/~johnsonj/permute/soda_submit.html
def permuta_jp(seed):
tam = len(seed)
newKey = key = tam - 1
while key > 0 and seed[key] <= seed[key-1]:
key -= 1
key -= 1
if key < 0: # chegou ao fim das permutações
return 0
while newKey > key and seed[newKey] <= seed[key]:
newKey -= 1
seed[key], seed[newKey] = seed[newKey], seed[key]
tam -= 1
key += 1
while tam > key:
seed[tam], seed[key] = seed[key], seed[tam]
key += 1
tam -= 1
return 1
def permutaJP(seed):
permuts = [seed[:]]
while permuta_jp(seed):
permuts.append(seed[:])
return permuts
def Ademir(seed):
return [x for x in Permutations(seed)]
def Niemeyer(seed):
return [x for x in permutation(seed)]
def Senra0(seed):
return permuta(Set(seed))
def Senra1(seed):
return nr_permuta_opt(seed)
def Senra2(seed):
return permuta_opt(seed)
def JP(seed):
return permutaJP(seed)
#def Senra3(seed):
# return permuta_opt2(seed)
def Show(iterable):
for i in iterable:
print i
from timeit import Timer
run = { 'Ademir':[],
#'Senra3':[],
'Senra2':[], 'Senra1':[], 'Senra0':[], 'Niemeyer':[],
'JP': []}
perm_sizes = (3,4,5)
for q in perm_sizes:
seed = range(q)
for r,l in run.items():
t = Timer('%s(seed)'%r, 'from __main__ import %s, seed'%r)
try:
l.append(t.timeit(1000))
except:
t.print_exc()
for r,l in run.items():
print r, l
</code>
Gustavo Barbieri
On Apr 1, 2005 3:00 PM, Diogo David Lima <diogoda...@yahoo.com.br> wrote:
> to brincando de fazer um programa com struct no python... alguem sabe onde
> tem exemplos disso na internet?
http://starship.python.net/crew/theller/pyhelp.cgi?keyword=struct
o que resulta em: http://www.python.org/doc/2.3/lib/module-struct.html
Mas provavelmente não é isso que você quer. Isto serve para ler dados
binários que estavam na forma empacotada.
Caso você queria fazer estruturas de dados em Python, deve utilizar classes:
class MinhaStrut:
def __init__( self ):
self.nome
self.idade
É como com o java, eles aboliram o "struct" devido as funcionalidades
já estarem nas classes.
> e qual funcao substitui o Getch() do C++?
Provavelmente você é do mundo windows?
http://www.python.org/doc/2.3/lib/module-msvcrt.html
Mas para ler entradas de teclado pode usar o input( "prompt" ) ou
raw_input( "prompt" )
http://www.python.org/doc/2.3/lib/module-msvcrt.html
> Qual funcao eu uso para fechar o programa?
Como assim fechar? sys.exit() termina a execução, mas o programa
termina normalmente ao chegar ao fim do script. Especifique melhor.
> Devia ter um guia de migração de c++ pra python! hehe
Deveria tentar ler o manual de referência ;-)
Use http://starship.python.net/crew/theller/pyhelp.cgi para procurar
na documentação
--
Gustavo Sverzut Barbieri
---------------------------------------
Computer Engineer 2001 - UNICAMP
GPSL - Grupo Pro Software Livre
Cell..: +55 (19) 9165 8010
Jabber: gsbar...@jabber.org
ICQ#: 17249123
MSN: barb...@gmail.com
GPG: 0xB640E1A2 @ wwwkeys.pgp.net
Rodrigo Dias Arruda Senra
> On Friday 01 April 2005 02:10, Rodrigo Dias Arruda Senra wrote:
> > A idéia que eu tive foi alocar espaço para todas as permutações,
> > empilhar estes vetores e simplesmente ir distribuindo os números
> > pelos espaços alocados, usando as diagonais.
Como o João sacou, esta idéia não funciona.
Para o primeiro elemento eu posso fazer a distribuição diagonal (ou qualquer que seja),
que ele irá satisfazer a propriedade:
número de ocorrências de um elemento (em um dado índice) == n!/n
Ou seja para S=(1,2,3) o 1 vai aparecer 2 vezes em cada posição
dentre as 3!==6 permutações.
O *bug na idéia* é que a propriedade acima não é a única
ser satisfeita! Outra propriedade que deve ser satisfeita é a não-repetição
de uma dada permutação. E minha meta era evitar isso por construção,
ao invés de verificação.
O algoritmo que propus estava *errado* pois gera n!/n conjuntos repetidos
de permutações. Porém parecia funcionar para len(S)==1 e len(S)==2
simplesmente porque 1!/1==2!/2==1 repetição.
[ JS ]:
-------
> Peraí
> Cada combina=E7=E3o de 1,2 aparece duas vezes acima...
> e n=E3o tem nenhuma combina=E7=E3o em que o 2 preceda o 1.
Como o JS observou *muito bem*, falha para len(S)==3, gerando
3!/3==6/3==2 repetições.
> > 1 2 3 \
> > 3 1 2 |
> > 2 3 1 /
> > 1 2 3 \
> > 3 1 2 |
> > 2 3 1 /
[ JS ]:
-------
> Não vi como ficou seu código, mas em vez de diagonal - digamos que o índice
> do número que estamos distribuindo em uma dada passagem - =
> então , em vez de incrementar i a cada linha da distribuição
> incrementar i a cada (n - 1) ! linhas, onde n é tamanho do vetor
> ordenado da posição que estamso distribuindo até o fim.
> Deixa ver:
> 1 2 _
> 1 _ 2
> 2 1 _
> _ 1 2 #em caso de colisão, i + =1
> 2 _ 1
> _ 2 1
Também *não* funciona, no espírito original do algoritmo
que era distribuir os números nas posições corretas sem *verificar* colisões.
A verificação recai nos casos anteriores que usavam "not in" e diferença de
conjuntos para _buscar_ novas permutações.
Eu não tenho uma solução ainda para essa abordagem, mas a
minha intuição sugere que talvez permutar a posição dos vetores
após a distribuição de cada elemento pode ser um caminho.
Logo, por favor desconsiderem os não-algoritmos Senra2 e Senra3,
que só resolvem n!/n do problema de permutar n elementos =)
A escala de desempenho está assim (do mais rápido p/ mais lento):
1) Não-recursivo, usando apenas listas, calculando todas permutações simultaneamente, sem geradores
2) Recursivo, usando múltplas listas, calculando serialmente as permutações, com geradores
3) Não recursivo, usando uma única fila, calculando serialmente as permutações, com geradores
4) Recursivo, usando tuplas e conjuntos, calculando uma permutação de cada vez, sem geradores
Análise Empírica do tempo de execução
----------------------------------------------------------
1) é 2x mais rápido que 2)~3) que são 5x mais rápidos que 4)
Análise Empírica do consumo de memória
-------------------------------------------------------------
Deixada como exercício para o leitor.
Análise assintótica do tempo de execução
------------------------------------------------------------
Não estou motivado o suficiente para ir atrás deste objetivo ;o)
Mas sobrando um tempinho vou "consultar os Universitários":
Donald Knuth e Robert Sedgewick. Aí conto aqui o que encontrar a
respeito (a menos que alguém seja mais rápido do que eu e faça
isso antes <wink>)
Abração,
Senra
--
,_
| ) 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 Dias Arruda Senra
[ "Joao S. O. Bueno Calligaris" <gwi...@mpc.com.br> ]
-----------------------------------------------
|
| Com tanat gente fazendo também quero... :-)
É isso aí!
| Na verdade - nada de novo:
| estou implementando a idéia que deu errado do Senra com a correção que
| eu sugeri: deslocar um número dentro do vetor só a cada contagem de
| i! , sendo i a distância do número até o fim do vetor, dada a ordem
| inicial.
| não precidsei de recursão, nem de "in" ...
É verdade
| um motne de comparações com None e etc...
Estas (comparações com None e if's==etc) estão no algoritmo.
Mas não é demérito nenhum. Eu só fiz o comentário sobre
comparações no e-mail passado, pois o algoritmo *bugado*
não fazia *nenhuma* comparação. Por isso que eu disse
que eles eram diferentes em espírito.
Mas legal que ele te _inspirou_ a cozinhar esta versão.
E o desempenho foi bom, veja + abaixo.
| afinal, a hora que isso começa a influir na velocidade
| de um projeto, hora de ir para C.
Não é questão de economizar um if aqui ou ali.
É que em análise de algoritmos define-se uma operação
básica como métrica. Em algoritmos de ordenação normalmente
esta métrica são as comparações (nos algoritmos baseados
em comparação -- a maioria).
Permutações tem tudo haver com ordenações, por isso surgiu a
idéia de calcular permutações sem fazer comparações, e daí
todo o meu blá blá blá passado.
| A sim..até fiz uma verficação por um erro que não acontece no meio do
| loop...nào fui capaz de deixar uma brecha para um loop infinito se a
| função fosse chamada com argumentos errados.
Tudo bem, nenhum dos outros algoritmos fez este tipo de teste.
| Não segui o código original do Senra - só copiei o cálculo de fatorial
| de lá.
Ok.
| Quem estiver fazendo os benchmarks ai..boa sorte...
Bom, acho que sou eu =)
Vamos lá. Para quem chegou nesta thread agora, os nomes abaixo
se referem a quem propôs o algoritmo para a lista python-brasil
(não necessariamente para o mundo =), em caso de dúvidas ler
o histórico da lista:
Truth lies on statistics:
--------------------------------
N.d.T ( A verdade reside|mente na Estatística)
Permutações com (3,4,5,6) elementos inteiros:
# Não-recursivo, usando uma única lista, calculando serialmente permutações in-place, sem geradores
JP ['0.0102', '0.0132', '0.0144', '0.0237']
# Recursivo, OO, usando uma única lista, calculando serialmente permutações, sem geradores
JS ['0.2189', '0.1703', '0.2890', '0.2878']
# Não-recursivo, usando apenas listas, calculando todas permutações simultaneamente, sem geradores
Senra1 ['0.1114', '0.4208', '2.3044', '14.7864']
# Recursivo, usando múltplas listas, calculando serialmente as permutações, com geradores
Ademir ['0.1762', '0.9102', '4.5213', '28.8839']
# Não recursivo, usando uma única fila, calculando serialmente as permutações, com geradores
Niemeyer ['0.1931', '0.9228', '5.9094', '40.5704']
# Recursivo, usando tuplas e conjuntos, calculando uma permutação de cada vez, sem geradores
Senra0 ['0.9033', '3.9008', '19.8232', '121.2006']
Duas conclusões importantes:
1) Cuidado na hora de definir seus casos de teste (quanto mais amplo melhor)
2) Quando disserem que Python é lento, olhe primeiro para o algoritmo.
Detalhe, ainda acho que há espaço para melhora!
Abração
Senra
--
,_
| ) 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___(|_|] -----------------------------------------------