sábado, 28 de novembro de 2009

Problema 8.7

Vamos apresentar uma solução básica para esta questão ... básica. O leitor é chamado a estudar o resultado e tentar entender como, e porque, funciona. Ter feito os problemas 8.1 a 8.7 ajuda! O mais importante a reter é que usamos diferentes representações internas (o que é manipulado no interior pelo programa) e externas (o que é visualizado no écran). Refira-se ainda que a palavra secreta é guardada na forma de um dicionário, onde as chaves são os caracteres e os valores os índices na cadeia onde esses caracteres ocorrem. É usada para alterar de modo expedito o estado da palavra que o utilizador vai construindo.


import random

def hang87():
# inicialização
# --- palavra secreta
palavras = open('/tempo/data/palavras.txt').read().split()
secreta = list(random.choice(palavras))
dicio = seq_to_dict(secreta)
# --- parâmetros
TAMANHO = len(secreta)
LIMITE = limite(TAMANHO)

pal_utilizador = list('_'* TAMANHO)
acertou = False
letras_usadas = []

# Entra no jogo
for tentativa in range(LIMITE):
# estado actual
mostra_palavra(pal_utilizador)
# joga
letra = adivinha(letras_usadas)
# analisa resposta
if letra in dicio:
# --- Acertou na letra!
indices = dicio[letra]
for ind in indices:
pal_utilizador[ind] = letra
# --- Acertou na palavra??
if fim(secreta,pal_utilizador):
acertou = True
mensagem_sim(secreta)
break
# actualiza estado
letras_usadas.append(letra)
# mensagem final
mensagem_fim(acertou,secreta)



# Auxiliares

def adivinha(letras_usadas):
"""Tenta mais uma letra."""
letra = raw_input('Escolha uma letra: ')
# verifica letra - ciclo
while letra in letras_usadas:
print
print '*** Letra já usada. Escolha outra sff!***'
print
letra = raw_input('Escolha uma letra: ')
return letra

def limite(tam_palavra):
""" para mais tarde se poder generalizar..."""
return tam_palavra

def mensagem_sim(secreta):
print
print 'Uau! Acertou!'
mostra_palavra(secreta)
print

def mensagem_fim(acertou,secreta):
if not acertou:
print 'Oops! Esgotaram-se as suas hipóteses...'
print 'A palavra secreta era: '
mostra_palavra(secreta)
print 'See you!'

def mostra_palavra(palavra):
""" mostra uma plavra formada por caracteres guardados numa lista."""
pal = ' '.join(palavra)
print 'Palavra:'
print pal
print

def fim(secreta, utilizador):
return secreta == utilizador


# --- Importante
def seq_to_dict(palavra):
"""
Transforma uma palavra num dicionário de chave os caracteres e
valores a lista dos índices.
"""
dicio = {}
for indice,letra in enumerate(palavra):
dicio[letra] = dicio.get(letra,[])+[indice]
return dicio

if __name__ == '__main__':
hang87()

Problema 7.10

Comparando com o problema 7.8 pouco há a dizer. Tudo se resume à gestão dos pixeis que devem ter o mesmo valor nas posições simétricas relativamente ao eixo dos xs.


import cImage

def espelho_v_s(imagem_fich):
"""Faz o espelho vertical de uma imagem.
Usa a parte superior."""
imagem = cImage.FileImage(imagem_fich)
largura = imagem.getWidth()
altura = imagem.getHeight()

nova_imagem = cImage.EmptyImage(largura,altura)
for coluna in range(largura):
for linha in range(altura/2):
pixel = imagem.getPixel(coluna, linha)
nova_imagem.setPixel(coluna,linha,pixel)
nova_imagem.setPixel(coluna,altura - linha - 1,pixel)
return nova_imagem


def main710(nome_fich):
# Prepara
imagem = cImage.FileImage(nome_fich)
largura = imagem.getWidth()
altura = imagem.getHeight()
# Converte
nova_imagem = espelho_v_s(nome_fich)
# Cria janela
janela = cImage.ImageWin('Espelho Vertical Superior',2*largura ,altura )
# Mostra
imagem.draw(janela)
nova_imagem.setPosition(largura,0)
nova_imagem.draw(janela)
# Termina
janela.exitOnClick()

if __name__ == '__main__':
main710('/tempo/imagens/duck3.jpg')


A respectiva imagem:


Problema 7.8

Estes problemas com imagens são todos muito parecidos. No caso da obtenção da versão a preto e branco, o mais relevante é sabermos que a imagem se obtém por comparação com um limiar. Esse limiar vai ser comparado com o valor na escala de cinzentos do pixel. Valores inferiores ficam preto (0,0,0), valores maiores ou iguais ficam brancos (255,255,255). Quanto ao mais é mais do mesmo: dois ciclos imbricados, criação da janela, transformação da imagem, posicionamento das imagens, desenho na tela e terminar.


import cImage

# 7.8
def preto_branco(imagem_fich, limiar):
""" Transforma para imagem a preto e branco."""

imagem = cImage.FileImage(imagem_fich)
largura = imagem.getWidth()
altura = imagem.getHeight()

nova_imagem=cImage.EmptyImage(largura,altura)

for coluna in range(largura):
for linha in range(altura):
pixel = imagem.getPixel(coluna,linha)
pixel_aux = pixel_cinzento(pixel)
if pixel_aux.getRed() < limiar :
novo_pixel = cImage.Pixel(0,0,0)
else:
novo_pixel = cImage.Pixel(255,255,255)
nova_imagem.setPixel(coluna,linha,novo_pixel)

return nova_imagem

def pixel_cinzento(pixel):
""" Converte um pixel para escala de cinzentos."""
vermelho = pixel.getRed()
verde = pixel.getGreen()
azul = pixel.getBlue()

int_media = (vermelho + verde + azul) / 3
novo_pixel = cImage.Pixel(int_media,int_media, int_media)
return novo_pixel

def main78(nome_fich,limiar):
# Prepara
imagem = cImage.FileImage(nome_fich)
largura = imagem.getWidth()
altura = imagem.getHeight()
# Converte
nova_imagem = preto_branco(nome_fich,limiar)
# Cria janela
janela = cImage.ImageWin('Preto e Branco',2*largura ,altura )
# Mostra
imagem.draw(janela)
nova_imagem.setPosition(largura,0)
nova_imagem.draw(janela)
# Termina
janela.exitOnClick()

if __name__ == '__main__':
main78('/tempo/imagens/duck3.jpg', 128)

Executando o código para a imagem e limiar dados, obtemos a imagem seguinte.



terça-feira, 24 de novembro de 2009

Problema 7.3

Vamos beneficiar dos ensinamentos do exemplo 7.2. Já sabemos quais são os famosos três passos:


(1) Definir uma janela onde possam ser colocados os objectos;
(2) Gerar as imagens
(3) Posicionar as imagens e mostrar na janela


Reflectindo sobre o problema, não é difícil chegar à conclusão de que vamos andar a colocar quadriláteros de diferentes dimensões na nossa tela. Notar que as linhas são na realidade quadriláteros de pequena espessura. Podemos por isso modularizar o nosso programa desenvolvendo sub-programas que podem ser reutilizados!

Dito isto, uma solução possível é a seguinte:

def quadrilatero(lado_1,lado_2,cor):
"""
Cria uma figura rectangular, colorida.
"""
imagem = cImage.EmptyImage(lado_1,lado_2)
pixel = cImage.Pixel(cor[0],cor[1],cor[2])
for coluna in range(lado_1):
for linha in range(lado_2):
imagem.setPixel(coluna,linha,pixel)
return imagem

def cria_e_mostra(lado_1,lado_2, cor, pos,janela):
imagem = quadrilatero(lado_1,lado_2,cor)
imagem.setPosition(pos[0],pos[1])
imagem.draw(janela)

def main():
janela = cImage.ImageWin('Mondrian',600,600)
# cria imagem, posiciona e mostra
cria_e_mostra(400,400,(255,0,0),(200,0),janela)
cria_e_mostra(200,200,(0,0,255),(0,400),janela)
cria_e_mostra(50,100,(255,255,0),(550,500),janela)
cria_e_mostra(10,600,(0,0,0),(190,0),janela)
cria_e_mostra(190,20,(0,0,0),(0,150),janela)
cria_e_mostra(600,10,(0,0,0),(0,390),janela)
cria_e_mostra(5,200,(0,0,0),(545,400),janela)
cria_e_mostra(50,10,(0,0,0),(550,500),janela)
# finito!
janela.exitOnClick()


No programa main temos os três passos bem identificados. A definição quadrilatero permite criar todas as formas necessárias. Compare com quadrado do problema 7.2. Finalmente, cria_e_mostra trata de criar as diferentes imagens, posicioná-las e mostrar na janela. Com os valores da figura o boneco é o apresentado na figura.



Problema 7.2

O enunciado do problema diz o seguinte:

Pretende colorir o chão da sua cozinha com quadrados coloridos. As cores devem ser colocadas de acordo com um padrão. A figura abaixo mostra um exemplo possível. A escolha das duas cores é sua!



Vamos reflectir. Olhando para a figura acima vemos que existe um padrão: os quadrados são colocados de modo alternado. Por outro lado, como é dito no enunciado, as formas são quadradas. Finalmente, embora na imagem a cozinha tenha uma dimensão 4 x 3, nó queremos uma solução geral, ou seja, para cozinhas de dimensão n x m. Do ponto de vista informático o que precisamos fazer? De acordo com o princípio geral deste tipo de aplicações vamos ter que responder a três sub-problemas:

(1) Definir uma janela onde possam ser colocados os azulejos;
(2) Gerar os quadrados de duas cores
(3) Posicionar os quadrados e mostrar na janela

A primeira questão, obriga-nos a saber a dimensão dos quadrados e as dimensões n x m da cozinha. Claro que as duas cores também são importantes. Mas disso trataremos de seguida. Daí o nosso programa principal poder ser definido do seguinte modo:


def main1(nx,ny,lado,cores):
janela = cImage.ImageWin('Ladrilhos',nx * lado, ny*lado)
# -- resto do programa a definir aqui
janela.exitOnclick()

A segunda questão, remete para a geração de quadrados coloridos. Trata-se de uma questão geral, pelo que a solução para o problema de gerar quadrados de duas cores diferentes pode ser resolvido por um único programa:

def quadrado(lado,cor):
"""
Cria um quadrado colorido de lado.
"""
imagem = cImage.EmptyImage(lado,lado)
pixel = cImage.Pixel(cor[0],cor[1],cor[2])
for linha in range(lado):
for coluna in range(lado):
imagem.setPixel(coluna,linha,pixel)
return imagem


Como se pode ver, começamos por criar uma imagem vazia, com as dimensões apropriadas. Depois definimos um pixel com a cor apropriada. A indicação da cor é dada por um tuplo com os valores (r,g,b). Finalmente, colocamos o pixel em cada ponto da imagem.

Falta agora a parte mais difícil, a questão três: posicionar os quadrados e mostrar a imagem. Pensemos um pouco e olhemos para a figura, que ilustra o caso de quadrados 2 x 2, para serem colocados numa cozinha 4 x 3:




Os círculos alaranjados indicam os pontos onde cada quadrado deve começar a ser desenhado. Correspondem aos índices de uma matriz 4 x 3. (0,0), (1,0), (2,0) ....É aí que devemos colocar as imagens. Mas, é claro, que neste caso estes pontos estão afastados entre si do valor do lado. Assim, na realidade, em termos da imagem, esses pontos são (0,0), (lado,0), (2*lado, 0), ..... Assim o problema reduz-se a colocar 4 x 3 = 12 imagens nas posições referidas. Isso faz-se com dois ciclos for, um dentro do outro que são gerados os índices da matriz, calculando-se em função deles o posicionamento na imagem. Para simplificar admitamos, por agora, que os quadrados são todos da mesma cor:


def cozinha_mono(nx,ny,lado, cor, janela):
""" Desenha os azulejos todos da mesma cor."""
for coluna in range(nx):
for linha in range(ny):
imagem = quadrado(lado, cor)
imagem.setPosition(coluna * lado,linha * lado)
imagem.draw(janela)

Se executarmos o programa apenas vemos desenhar uma cozinha com o chão todo da mesma cor. Não é muito impressionante! Então com alternar entre duas cores?? Um modo possível é notar que a soma das posições (x,y) do canto superior esquerdo das imagens são, alternadamente, pares e ímpares. E sabermos como determinar se um número é par. Logo:

def cozinha_poli(nx,ny,lado, cores, janela):
""" Desenha os azulejos com duas cores alternadas."""
for coluna in range(nx):
for linha in range(ny):
if (coluna + linha)%2 == 0:
# par
imagem = quadrado(lado, cores[0])
else:
# ímpar
imagem = quadrado(lado, cores[1])

imagem.setPosition(coluna * lado,linha * lado)
imagem.draw(janela)

Juntando agora todas as peças temos o programa completo:


import cImage

def cozinha_mono(nx,ny,lado, cor, janela):
""" Desenha os azulejos todos da mesma cor."""
for coluna in range(nx):
for linha in range(ny):
imagem = quadrado(lado, cor)
imagem.setPosition(coluna * lado,linha * lado)
imagem.draw(janela)

def cozinha_poli(nx,ny,lado, cores, janela):
""" Desenha os azulejos com duas cores alternadas."""
for coluna in range(nx):
for linha in range(ny):
if (coluna + linha)%2 == 0:
# par
imagem = quadrado(lado, cores[0])
else:
# ímpar
imagem = quadrado(lado, cores[1])

imagem.setPosition(coluna * lado,linha * lado)
imagem.draw(janela)

def quadrado(lado,cor):
"""
Cria um quadrado colorido de lado.
"""
imagem = cImage.EmptyImage(lado,lado)
pixel = cImage.Pixel(cor[0],cor[1],cor[2])
for linha in range(lado):
for coluna in range(lado):
imagem.setPixel(coluna,linha,pixel)
return imagem

def main1(nx,ny,lado,cores):
janela = cImage.ImageWin('Ladrilhos',nx * lado, ny*lado)
cozinha_poli(nx,ny,lado,cores, janela)
janela.exitOnClick()

if __name__=='__main__':
main1(4,3,50,[(255,0,0),(0,0,255)])

Se quisermos variar nas cores e ter alguma surpresa basta fazer uma pequena mudança no programa principal:

def main2(nx,ny,lado):
janela = cImage.ImageWin('Ladrilhos',nx * lado, ny*lado)
# escolhe cores aleatoriamente
cores= []
for i in range(2):
r = random.randint(0,255)
g= random.randint(0,255)
b = random.randint(0,255)
while (r,g,b) in cores:
r = random.randint(0,255)
g= random.randint(0,255)
b = random.randint(0,255)
cores.append((r,g,b))

cozinha_poli(nx,ny,lado,cores, janela)
janela.exitOnClick()


Os mais puristas poderão criar um programa à parte para produzir uma lista de cores diferentes de tamanho variável:

def gera_cores(n):
“”” Gera uma lista de n cores.”””
cores= []
for i in range(n):
r = random.randint(0,255)
g= random.randint(0,255)
b = random.randint(0,255)
while (r,g,b) in cores:
r = random.randint(0,255)
g= random.randint(0,255)
b = random.randint(0,255)
cores.append((r,g,b))

segunda-feira, 23 de novembro de 2009

Imagens

Na aula teórica estudámos o módulo cImage, que permite algumas manipulações simples de imagens. Explorámos mais tarde nas aulas TP as capacidades do módulo em resolver alguns dos problemas normais que queremos resolver com imagens. Este pequeno exemplo pretende apenas chamar a atenção para os três aspectos (fases) envolvidos na manipulação de imagens:


(1): criação de uma janela

(2): obtenção/criação de imagens

(3): colocação das imagens na janela e sua visualização


Vejamos então o exemplo.

import cImage

def mostra_imagem(imagem,pos,janela):
"""
Mostra imagem numa dada posição da janela.
"""
imagem.setPosition(pos[0],pos[1])
imagem.draw(janela)

def cria_imagem(largura,altura, r,g,b):
“””
Cria imagem a partir de nada...
“””
imagem = cImage.EmptyImage(largura,altura)
pixel = cImage.Pixel(r,g,b)
for coluna in range(largura):
for linha in range(altura):
imagem.setPixel(coluna,linha,pixel)
return imagem

def main(largura,altura):
“”” As três fases.”””
# Cria janela
janela = cImage.ImageWin('Toto',largura,altura)
# Cria imagem
imagem = cria_imagem(largura/3,altura/2,255,0,0)
# Coloca imagem na janela e mostra
mostra_imagem(imagem,(50,100),janela)
janela.exitOnClick()

if __name__=='__main__':
main(600,400)

Analisemos o programa. Comecemos pela definição main. Ela faz o papel do nosso programa principal. Estão claramente identificadas as três fases acima referidas. Para definir a janela temos que lhe dar um nome (‘Toto’ neste caso) e as suas dimensões (largura e altura). De seguida, a definição cria_imagem é responsável por criar uma imagem simples, em que todos os pixeis são da mesma cor (r,g,b). Note-se como se cria um pixel (linha 15). Não basta indicar um tuplo com os valores das intensidades nos três canais de cor! Outro aspecto importante é o facto de estarmos a lidar com imagens 2D. Isso significa que cada pixel vai ser identificado pelas suas coordenadas em largura e em altura. Como se fosse uma matriz. Assim, navegar por uma imagem, seja para criar, analisar ou modificar, obriga, regra geral, a dois ciclos for, um dentro do outro (linhas 16-18). Ver a imagem obriga a duas coisas: definir a posição onde a imagem vai ser colocada, através da identificação explícita do seu canto superior esquerdo (linha 7 ) e, a seguir mandar desenhar (linha 8 ).
Executando este programa o resultado é a imagem que se pode ver abaixo.


quinta-feira, 19 de novembro de 2009

Mini Teste # 2

Pergunta 2.1


Diga o que entende por aliasing. Pode usar um exemplo como auxiliar da sua justificação.
Resposta

Falamos de aliasing quando nomes distintos ficam associados (pela identidade) ao mesmo objecto.
Exemplo:

>>> a = 5
>>> b = 5

>>> a = [1,2,3]
>>> b= a


Pergunta 2.2

Explique de modo claro, sintético e rigoroso o que aconteceu na sessão seguinte:


>>> def prod(x,y):
... return x * y
...
>>> a = 5
>>> print prod(a,3)
15
>>> a
5
>>> x
Traceback (most recent call last):
File "", line 1, in
NameError: name 'x' is not defined
>>>

Resposta

Nas linhas 1 e 2 definimos uma função de nome prod. Na linha 4, associamos o nome a ao objecto inteiro 5. Na linha 5, usamos a definição prod, sendo o resultado devolvido impresso por força da instrução print. Quando usamos a definição prod os parâmetros formais x e y vão ficar associados aos parâmetros reais a e 3, como se se tivesse feito no inicio de prod x=a e y = 3. A linha 6 mostra o resultado de executar o comando da linha 5.Na linha 7 perguntamos pelo objecto associado a a , e a resposta é dada na linha 8. Tentamos fazer o mesmo na linha 9 para x, mas dá erro pois x é um parâmetro formal da definição prod e, como tal, só existe no interior da definição.

Pergunta 2.3


Admitindo que n é um número inteiro positivo, explique o que faz o programa da listagem abaixo. A sua resposta não pode ser baseada em generalidades. Em concreto, queremos saber para cada valor de n qual o valor devolvido pela instrução return.

def misterio(n):
res = [0]
for i in range(1,n+1):
res.append(res[-1] + i)
return res[-1]

Resposta

Calcula o somatorio de 1 a n. O processo é iterativo, calculando-se primeiro os diferente somatórios de 1 a i. No final ao devolver o elemento na última posição (res[-1]), este é o valor da soma de todos os elementos.

Pergunta 2.4

Numa das fichas abordámos as árvores genealógicas e referimos que podiam ser organizadas através de um dicionário. As chaves são nomes, e os valores são listas de nomes dos descendentes directos (isto é, filhos(as)). Desenvolva um programa que, dados um dicionário, cujo conteúdo é uma árvore genealógica, e dois nomes, determina se esses dois nomes são primos(as) em primeiro grau. Relembramos que duas pessoas são primas entre si, se são filhos(as) de dois(duas) irmãos(ãs).

Exemplificando:

>>> dic = {'ernesto':['carlos', 'jorge','ana'], 'carlos':['ricardo', 'joana'],
'joana': [], 'jorge':['carla', 'francisca'], 'ana':[], 'ricardo':['sara']}
>>> <------- A sua definicão aqui
>>> print primos(dic,'ricardo','francisca')
True
>>>


Resposta


def primos(dicio,nome1,nome2):
"""
Primos são os filhos de dois irmãos...
"""
prog1 = progenitor(dicio,nome1)
prog2 = progenitor(dicio,nome2)
return (prog1 != prog2) and irmaos(dicio,prog1,prog2)

def irmaos(dic,nome1,nome2):
""" Têm o mesmo progenitor?"""
prog1 = progenitor(dic, nome1)
prog2 = progenitor (dic,nome2)
return prog1 == prog2

def progenitor(dic, nome):
""" Devolve o progenitor do nome."""
for chave, valor in dic.items():
if nome in valor:
return chave
return []

Pergunta 2.5

Suponha que está perdido no meio de uma cidade e não tem GPS para se orientar. Pergunta a um transeunte como pode chegar ao seu destino. Como a cidade é geométrica a resposta é fácil. Recebemos uma sequência de indicações do tipo vira à esquerda (E), depois avança (A), depois roda à direita (D), depois avança (A), depois avança de novo (A), depois recua (R), etc.. Usando o módulo cTurtle desenvolva um programa, que quando executado, simule com a tartaruga os seus movimentos quando esta executa os comandos recebidos.
A imagem mostra o que acontece quando manda correr o programa geral main_tarta(). Por conveniência de visualização marcámos o inicio e o fim do percurso com pontos, verde e vermelho, respectivamente. O seu programa chama-se, no código abaixo, navega.





def main_tarta():
tartaruga = cTurtle.Turtle()
tartaruga.setheading(0)
comandos = 'ADAEAERDAAEARA'
navega(comandos, tartaruga)
tartaruga.exitOnClick()


Resposta


def navega(comandos, tartaruga):
"""
Navega numa cidade matricial.
Conversão simples.
"""
tartaruga.shape('turtle')
tartaruga.dot(20,'green')
for comando in comandos:
if comando == 'E':
tartaruga.left(90)
elif comando == 'D':
tartaruga.right(90)
elif comando == 'A':
tartaruga.forward(50)
elif comando == 'R':
tartaruga.back(50)
else:
print 'Comando desconhecido...'
break
tartaruga.dot(20,'red')

terça-feira, 17 de novembro de 2009

Dicionários, álgebra e outras coisas misteriosas...

O princípio da economia é cada vez mais fundamental na nossa vida. Em programação, isso significa, entre outras coisas, poupar nos recursos da máquina, por exemplo na memória. Para conseguir essa poupança recorre-se a representações dos dados que sejam económicas passando para os algoritmos a tarefa de manipular essas representações. Que mecanismos de representação de dados temos em Python? Bom, para dados não numéricos, as listas e os dicionários. Parece pouco, mas na realidade estes dois tipos de contentores resolvem, quase sempre de modo elegante, a questão da representação. Vejamos um exemplo.


Suponhamos que queremos manipular vectores esparsos. Estes vectores caracterizam-se por ter quase todas as posições a 0. Como representar? Uma solução interessante é usar um dicionário em que a chave é o índice do vector e, o valor, o valor nessa posição. Assim:


O vector: [2,0,0,0,0,3,0,0,0,4,0,0,0] origina o dicionário = {0:2,5:3,9:4}


Agora temos que resolver a questão das operações. Escolhemos duas: soma e produto escalar. Na soma, somam-se os valores com o mesmo índice. No produto, multiplicam-se os valores nas mesmas posições e, no final, somam-se esses produtos. Eis o resultado:

def soma_vec(v1,v2):
""" soma dois vectores esparsos, organizados como dicionários.
vec = [2,0,0,0,0,3,0,0,0,4,0,0,0] --> {0:2,5:3,9:4}
"""
v = v1.copy()
for ch in v2.keys():
v[ch] = v.get(ch,0) + v2[ch]
return v

def dot_produto(v1,v2):
""" Produto escalar dois vectores organizados como dicionários.
vec = [2,0,0,0,0,3,0,0,0,4,0,0,0] --> {0:2,5:3,9:4}
"""
v = dict()
for ch in v2:
if ch in v1:
v[ch] = v1[ch] * v2[ch]
prod = sum(v.values())
return prod

Notas. No caso da soma, criámos uma cópia de um dos dicionários originais. Porquê? No caso do produto, usámos o construtor do tipo dict(). O acesso às chaves pode ser feito, num ciclo, de dois modos distintos, for chave in dicio ou for chave in dicio.keys().


Uma referência final para os que usam Python 3.0 ou superior. A partir desta versão foi introduzido o conceito de vista. As operações dic.key(), dic.items() e dic.values() devolvem um iterável com características acrescidas: todas as mudanças dinâmicas que ocorrem no dicionário são imediatamente reflectidas na vista e, existem novas operações, do tipo das operações sobre conjuntos, que podem ser usadas com as vistas (intersecção, união, diferença, diferença simétrica). Usando essas novas potencialidades o nosso produto escalar pode ser implementado assim:

def dot_produto_b(v1,v2):
""" Produto escalar dois vectores organizados como dicionários.
vec = [2,0,0,0,0,3,0,0,0,4,0,0,0] --> {0:2,5:3,9:4}
Funciona apenas em Python 3.0 ou superior!
"""
v = dict()
for ch in (v1.keys() & v2.keys()):
v[ch] = v1[ch] * v2[ch]
prod = sum(v.values())
return prod

segunda-feira, 16 de novembro de 2009

Matrizes

Todos temos ideia do que são matrizes e das diversas operações que com elas podemos fazer. Existem em Python módulos que nos permitem manipular de forma eficiente matrizes, como por exemplo Numpy and SciPy. Também o pacote Matplotlib, e o módulo nele integrado pylab, permitem efectuar operações com matrizes. Mas, admitamos que não temos e que necessitamos de definir uma representação para matrizes e implementar as operações básicas. O modo mais correcto de o fazer seria definir um novo tipo de dados e implementá-lo como uma classe. Mas isso remete-nos para a programação orientada aos objectos, território ainda por nós não explorado. Vamos então caçar com gato.


Uma matriz vai ser representada como uma lista de listas. Cada elemento será uma linha da matriz. A partir desta decisão, as implementações das operações elementares decorrem naturalmente:


def addMatrix(A,B):
""" Soma duas matrizes."""
sizeL=len(A)
sizeC=len(A[0])
C=nullMatrix(sizeL,sizeC)
# Soma
for i in range(sizeL):
for j in range(sizeC):
C[i][j]=A[i][j]+B[i][j]
return C

def prodMatrix(A,B):
"""Multiplica duas matrizes."""
sizeL=len(A)
sizeC=len(A[0])
C=nullMatrix(sizeL,sizeC)
# Multiplica
for i in range(sizeL):
for j in range(sizeC):
val=0
for k in range(len(B[0])):
val = val + A[i][k]*B[k][j]
C[i][j]=val
return C

def transposeMatrix(M):
"""Calcula a transposta de uma matriz."""
aux=[]
for j in range(len(M[0])):
linha=[]
for i in range(len(M)):
linha.append(M[i][j])
aux.append(linha)
return aux

Como se nota estas operações têm todas uma forma semelhante, envolvendo um ciclo dentro de outro ciclo, isso mesmo consequência da representação escolhida. Para testar estas operações podemos definir operações auxiliares:

import random

def cria_matriz(lin,col):
A=[]
for i in range(lin):
linha=[]
for j in range(col):
linha = linha + [random.randint(1,10)]
A= A + [linha]
return A

def mostra_matriz(matriz):
print 'Matriz'
for i in range(len(matriz)):
for j in range(len(matriz[0])):
print matriz[i][j],'\t',
print
print '_' * 10

E pronto. Divirta-se!

A informática e a matemática

A informática pretende ter o rigor da matemática. Só que nem sempre é possível. Analisemos um caso particular da função logística e três modos de a definir, todos matematicamente equivalentes:

f(x) = 3.9*x*(1- x)
g(x) = 3.9*(x - x**2)
h(x) = 3.9*x - 3.9 * x * x

Vamos supor que queremos computar a órbita para o valor inicial de x= 0.35. Esse cálculo é feito iterando as funções definidoras, isto é produzindo a sequência:


x, f(x), f(f(x)), f(f(f(x))), ...
.

Vejamos o programa que faz os cálculos e que usa o módulo cTurtle para desenhar o gráfico.

import cTurtle

def grafico(funcao,inicio,num,cor):
"""
Faz o gráfico da função a partir do ponto inic.
"""
x=inicio
cTurtle.pencolor(cor)
cTurtle.up()
cTurtle.goto(0,x)
cTurtle.down()
cTurtle.dot(3)

for i in range(1,num):
x = funcao(x)
cTurtle.goto(i,x)
cTurtle.dot(3)

# Funções de teste
def f(x):
return 3.9*x*(1 - x)

def g(x):
return 3.9 * (x - x**2)

def h(x):
return 3.9*x - 3.9*x*x

def main(n):
cTurtle.setWorldCoordinates(-1.0,-0.1,n+1,1.1)
grafico(f,0.35,n,'red')
grafico(g,0.35,n,'green')
grafico(h,0.35,n,'blue')
cTurtle.mainloop()

O leitor mais atento notará que esta solução retoma o tema das funções como parâmetros das definições. Ao executar o programa, chamando main() veja o que acontece. O vídeo abaixo reproduz a parte final da execução. Se reparar, embora matematicamente equivalentes, na parte final os gráficos divergem de modo significativo. Porque será???

domingo, 15 de novembro de 2009

As funções são objectos (II)

Avancemos um pouco mais. Então se as funções são objectos como vimos e se , por isso, podem ser passadas como parâmetros numa definição, será que podem ser devolvidas como resultado? E a resposta é ... sim!

Consideremos o problema de, dada uma função e o seu domínio, traçar o respectivo gráfico. Vejamos uma solução possível que se socorre do módulo cTurtle.


def grafico(tartaruga,funcao, valores):
""" Desenha o gráfico da função f."""
tartaruga.up()
tartaruga.goto(valores[0], funcao(valores[0]))
tartaruga.down()

for indice in range(1,len(valores)):
tartaruga.goto(valores[indice], funcao(valores[indice]))

Como se pode ver, dada a lista dos valores de x, mandamos fazer o plot dos correspondentes f(x):

def main3():

xx = float_range.float_range_lista(-4,4,0.1)
tartaruga = cTurtle.Turtle()
tartaruga.pensize(3)
tartaruga.setWorldCoordinates(-4,-2,4,2)
linha(tartaruga,-4,0,4,0)
tartaruga.write('X', move=False, align='left', font=('Arial', 14, 'normal'))
linha(tartaruga,0,-2,0,2)

tartaruga.pencolor('red')
tartaruga.up()
tartaruga.goto(0.5,1)
tartaruga.write('SIN(X)', move=False, align='left', font=('Arial', 14, 'normal'))
grafico(tartaruga,math.sin,xx)

tartaruga. exitOnClick()

E o resultado está à vista:




Admitamos agora que queremos desenhar o gráfico de uma função que depende desta função. Por exemplo a derivada. Todos conhecemos a definição de derivada de uma função contínua:




Esta definição é válida para toda a função. Assim não nos pode espantar que se possa fazer:

def derivada(f):
"""Derivada de uma função."""
dx= 1.e-6
def d(x):
return (f(x + dx) - f(x))/dx
return d

Olhemos para o código. Temos uma nova definição derivada cujo argumento é uma função. Desta parte já falámos anteriormente. O seu corpo é feito apenas da construção de uma nova função que materializa a definição dada. Com esta definição, no interior de outra definição, estamos a criar um objecto do tipo função! É esse objecto que é devolvido. Repare-se que usamos uma constante muito pequena para dx. Juntando tudo e aplicando:

def main1():

xx = float_range.float_range_lista(-4,4,0.1)
tartaruga = cTurtle.Turtle()
tartaruga.pensize(3)
tartaruga.setWorldCoordinates(-4,-2,4,2)
linha(tartaruga,-4,0,4,0)
linha(tartaruga,0,-2,0,2)

tartaruga.pencolor('red')
grafico(tartaruga,math.cos,xx)
tartaruga.up()
tartaruga.goto(0.5,1)
tartaruga.write('COS', move=False, align='left', font=('Arial', 14, 'normal'))
tartaruga.down()

tartaruga.pencolor('blue')
tartaruga.up()
tartaruga.goto(-2,1.2)
tartaruga.write('DERIVADA COS', move=False, align='left', font=('Arial', 14, 'normal'))
tartaruga.down()
grafico(tartaruga,derivada(math.cos),xx)
tartaruga.exitOnClick()

Executando o programa obtém-se:



Fantástico, não é???

As funções são objectos

Já ouvimos várias vezes dizer que, em Python, tudo são objectos. Por exemplo, os números (inteiros ou não), as cadeias de caracteres, as listas, os dicionários, os ficheiros, tudo isso são objectos. Dizem-nos, vezes sem conta, que esses objectos têm três atributos fundamentais: identidade, valor e tipo. Quando queremos usar esses objectos podemos usar referência explícitas, como quando calculamos:


>>> 3 + 4
7
>>>

Mas o mais usual é darmos um nome ao objecto e passarmos a referir-mo-nos a esse objecto pelo seu nome:

>>> a = 5
>>> 5 + a
10
>>>

Sempre que usamos a instrução de atribuição criamos uma nova associação entre um nome e um objecto. É claro que um objecto pode ter vários nomes:


>>> a = 5
>>> b = a
>>> id(a)
16793944
>>> id(b)
16793944
>>> b
5
>>>

Mas o que se passa, quando definimos uma função, como em:

>>> def toto(x):
... return 2 * x
...
>>>

Criamos na mesma um objecto do tipo função:

>>> type(toto) # tipo
<type 'function'>
>>> id(toto) # identidade
13426544
>>> toto # valor
<function toto at 0xccdf70>
>>>

Neste caso a descrição do valor é mais complexa (), mas não deixa de ser um objecto. Então pode também ter vários nomes como acontece com os outros tipos de objectos? Claro!

>>> toto(5)
10
>>> tete = toto
>>> tete(5)
10
>>>

Bom, mas então põe-se outra questão. Quando eu defino algo, nessa definição posso ter parâmetros formais, ou argumentos. Na altura de usar o programa eu comunico quais os parâmetros reais e estabeleço uma relação, temporária, entre eles:

>>> a = 5
>>> toto(a)
10
>>>

Os parâmetros formais são sempre nomes de objectos. Os parâmetros reais podem ser nomes, objectos ou expressões cujo valor é uma referência para um objecto.
No exemplo dado, o parâmetro formal x da definição é associado ao parâmetro real a, aquando do uso da definição. Em termos práticos é como se, no início da execução do programa, se tivesse feito x = a, sendo que essa associação é válida durante a execução do programa, caso não seja alterada por outra associação. Mas, e regressamos à questão, será possível associar um parâmetro formal com uma definição? É possível:

>>> def toto(x):
... print x
...
>>> def main(f,x):
... f(x)
...
>>> main(toto,5)
5
>>>

O que é que aconteceu? Bem, durante o uso do programa main, o parâmetro formal f fica associado ao parâmetro real toto. Então, quando tenho a instrução f(x), durante a execução é como se tivesse toto(5). Esta ao ser executada, cumpre o seu papel e imprime 5. Mas esta possibilidade tem algum interesse? Claro que tem. Durante as aulas demos vários exemplos de código, por exemplo, código envolvendo imagens, em que é tudo idêntico menos uma pequena parte. Podemos transformar essa parte, por abstracção, numa nova definição, tornando assim o programa mais geral, mais legível e, pelo menos partes dele, reutilizável:

def manipula_imagem(imagem, funcao_cor):
""" Manipula uma imagem de acordo com uma função."""
largura = imagem.getWidth()
altura = imagem.getHeight()
nova_imagem = cImage.EmptyImage(largura,altura)

for coluna in range(largura):
for linha in range(altura):
pixel = imagem.getPixel(coluna,linha)
novo_pixel = funcao_cor(pixel)
nova_imagem.setPixel(coluna,linha, novo_pixel)
return nova_imagem

Este programa, apresentado nas aulas, pega numa imagem e transforma cada um dos seus pixeis de acordo com uma dada função. Diferentes funcao_cor, originam diferentes resultados:

def pixel_sepia(pixel):
""" Tempo do passado."""
r = pixel.getRed()
g = pixel.getGreen()
b = pixel.getBlue()

novo_r = (r * 0.393 + g * 0.769 + b * 0.189)
novo_g = (r * 0.349 + g * 0.686 + b * 0.168)
novo_b = (r * 0.272 + g * 0.534 + b * 0.131)
if novo_r > 255: novo_r = r
if novo_g > 255: novo_g = g
if novo_b > 255: novo_b = b

novo_pixel = cImage.Pixel(novo_r,novo_g,novo_b)
return novo_pixel

def pixel_cinzento(pixel):
""" Converte um pixel para escala de cinzentos."""
vermelho = pixel.getRed()
verde = pixel.getGreen()
azul = pixel.getBlue()

int_media = (vermelho + verde + azul) / 3
novo_pixel = cImage.Pixel(int_media,int_media, int_media)
return novo_pixel

pixel_sepia e pixel_cinzento são dois exemplos possíveis de funções de cor distintas.

Problema 6.18

A partir de um ficheiro com informação sobre clientes, e de uma carta circular, como gerar cartas para clientes que satisfazem determinado critério? Eis uma solução possível.


def gera_carta(carta,clientes):
"""
carta = texto geral da carta, num ficheiro.
clientes = dicionário com os dados dos clientes.
nome, data de nascimento (dd/mm/aaaa), morada, telefone
"""
PREFIXO = '/tempo/data/'
# lê carta
f_in = open(carta,'r')
texto_carta = f_in.read()
f_in.close()
# filtra clientes
lista_clientes = [(nome_cliente(cliente),morada_cliente(cliente)) for cliente in clientes.values() if (ano_cliente(cliente) < 1974)]

for numero in range(len(lista_clientes)):
# processa
saudacao = 'Caro(a)'
nome = lista_clientes[numero][0]
morada = lista_clientes[numero][1]
preambulo = saudacao+' '+nome + '\n' + morada + '\n\n'

f_out = open(PREFIXO+nome+str(numero)+'.txt','w')
f_out.write(preambulo)
f_out.write(texto_carta)
f_out.close



def dados(cliente):
nome,data,morada,telefone = cliente
dia, ano, mes = data.split('/')
return (nome, (int(dia),int(ano),int(mes)),morada, int(telefone))

def ano_cliente(cliente):
dados_cliente = dados(cliente)
ano = dados_cliente[1][2]
return ano

def nome_cliente(cliente):
dados_cliente = dados(cliente)
nome = dados_cliente[0]
return nome

def morada_cliente(cliente):
dados_cliente = dados(cliente)
morada = dados_cliente[2]
return morada

if __name__ == '__main__':
clientes = {100:('Ernesto','15/06/1953','F 26','239790019'),101:('Joana','29/09/2001','A 15','239700400'),102: ('Lurdes','17/06/1913','G 30','808242424'),103:('Daniela','31/03/2002','F 16','239400400')}
gera_carta('/tempo/data/carta.txt', clientes)


O que é que esta solução tem de especial? Bem, desde logo a sua estrutura lógica: primeiro lemos a carta, depois seleccionamos os clientes e, finalmente, geramos as cartas personalizadas. São possíveis muitas variantes à solução apresentada. Fica para a imaginação e implementação do leitor. Um outro aspecto digno de relevo foi o recurso à abstracção e modularização. Esse aspecto está evidenciado no conjunto de operações que acedem aos dados do cliente. Caso decidamos alterar a representação dos dados do cliente, basta apenas alterar estas operações não sendo necessário mexer no resto do programa. Isto é uma gande vantagem!

Problema 6.14

Neste exemplo o que queremos visualizar é a percentagem das ocorrências de somas. Para variar vamos usar o módulo pylab do pacote matplotlib. Vejamos o código.


import operator
import pylab

def le_ficheiro(nome):
f_in = open(nome,'r')
dados = []
linha = f_in.readline()
while linha !='' and linha != '\n':
pos = linha[:-1].split()
dados.append((int(pos[0]), int(pos[1])))
linha = f_in.readline()

f_in.close()
return dados

def analisa_frequencias(dados):
frequencias={}
for valor in dados:
frequencias[valor]=frequencias.get(valor,0)+1
# completa
for valor in range(1,13):
frequencias[valor] = frequencias.get(valor,0)
return frequencias


def visualiza_frequencias(ocorrencias):
""" A partir do dicionário das ocorrências produz o plot
das percentagens.
"""
lista_ocorrencias = ocorrencias.items()
lista_ocorrencias.sort(key=operator.itemgetter(0))
total = sum(ocorrencias.values())

percentagem = [ float(valor[1])/total for valor in lista_ocorrencias]
pylab.ylabel('Percentagem')
pylab.xlabel('Numeros')
xx = range(1,13)
pylab.plot(xx,percentagem, 'r-o')
pylab.show()



def main614(ficheiro):
# Leitura dos dados
pares = le_ficheiro(ficheiro)
soma_pares = [sum(par) for par in pares]
# Frequências
frequencias = analisa_frequencias(soma_pares)

# Visualização de frequências
visualiza_frequencias(frequencias)


Comecemos... pelo fim. O nosso programa principal, main614, divide o problema em tês partes: obtenção dos dados, cálculo das percentagens e visualização. A leitura dos dados no formato de pares por linha já foi visto várias vezes. Usamos listas por compreensão para transformar a lista de pares numa lista de somas de pares. O cálculo das percentagens socorre-se de um dicionário. Como podem existir somas que nunca ocorreram e cuja percentagem será zero, somos obrigados a vertificar esse facto colocando entradas no dicionário (número:0), nessas situações. Delegamos depois no pylab a tarefa de visualizar o resultado. Aqui surge a questão dos dicionários serem colecções não ordenadas de pares chave : valor. Por isso temos que passar tudo para uma lista, que é ordenada por chave. Feito isso, podemos mandar desenhar o gráfico. A imagem ilustra o que é mostrado.


Problema 6.13

Este problema vai ajudar a exercitar alguns aspectos. Desde logo o modo como guardamos os dados num dicionário. Mas também a possibilidade de usar o módulo cTurtle para visualizar os dados. Segue-se o programa.


import cTurtle

def le_ficheiro(nome):
f_in = open(nome,'r')
dados = []
linha = f_in.readline()
while linha !='' and linha != '\n':
pos = linha[:-1].split()
dados.append((int(pos[0]), int(pos[1])))
linha = f_in.readline()

f_in.close()
return dados


def analisa_frequencias(dados):
frequencias={}
for par in dados:
for i in range(2):
frequencias[par[i]]=frequencias.get(par[i],0)+1
return frequencias


def desenha_coluna(tartaruga, numero, altura):
x=(numero-1)*20 # para começar no inicio do eixo
y=altura *10

# escrever número no eixo
tartaruga.up()
tartaruga.goto(x+5,-20)
tartaruga.down()
tartaruga.write(str(numero), move=False, align='left', font=('Arial', 18, 'normal'))

#desenhar coluna
tartaruga.up()
tartaruga.goto(x+2,0)
tartaruga.down()
tartaruga.goto(x+2,y)
tartaruga.goto(x+18,y)
tartaruga.goto(x+18,0)

# escrever número da frequência
tartaruga.up()
tartaruga.goto(x+5,y+5)
tartaruga.down()
tartaruga.write(str(altura), move=False, align='left', font=('Arial', 10, 'normal'))


def visualiza_frequencias(tartaruga,frequencias):
# desenhar eixo dos x
tartaruga.up()
tartaruga.goto(0,0)
tartaruga.down()
tartaruga.goto(20*6,0)

# desenhar frequências
for i in range(1,7):
desenha_coluna(tartaruga,i,frequencias.get(i))

tartaruga.hideturtle()


def main613(ficheiro):
# Leitura dos dados
pares = le_ficheiro(ficheiro)
# Análise de frequências
frequencias=analisa_frequencias(pares)
# Visualização de frequências
tartaruga= cTurtle.Turtle()
visualiza_frequencias(tartaruga,frequencias)
tartaruga.exitOnClick()



A leitura de dados a partir de um ficheiro já é uma questão resolvida em problemas anteriores. Segue-se depois a contagem do número de ocorrências. Usamos um dicionário em que a chave é o número e o valor é igual ao número de vezes que ocorreu. A visualização é desdobrada em duas operações: uma, permite desenhar uma coluna e é usada por outra definição (visualiza_frequências) que percorre com um ciclo for os 6 números, imprimindo a coluna correspondente. Note-se o uso do comando de escrita de texto na tela e as suas opções (write).

Só falta transcrever o programa, executar e ... visualizar!

Problema 6.12

Este problema tem um enunciado simples mas vai originar um programa extenso. Temos que gerar pares de números e guardar os ditos num ficheiro num formado definido. Depois temos que ler os dados a partir do ficheiro, interpretá-los como coordenadas no plano, e usar uma tartaruga para desenhar segmentos de recta que unam esses pontos. Vejamos o código.


import random
import cTurtle

def gera_pares(n):
res = [(random.randint(1,6), random.randint(1,6)) for i in range(n)]
return res

def cria_ficheiro(nome,dados):
f_out = open(nome,'w')
for par in dados:
linha = str(par[0]) + '\t' + str(par[1]) + '\n'
f_out.write(linha)
f_out.close()

def le_ficheiro(nome):
f_in = open(nome,'r')
dados = []
linha = f_in.readline()
while linha !='' and linha != '\n':
pos = linha[:-1].split()
dados.append((int(pos[0]), int(pos[1])))
linha = f_in.readline()

f_in.close()
return dados

def visualiza(tartaruga,dados):
dados = [(20 * dado[0],20 * dado[1]) for dado in dados] # para se poder ver
tartaruga.up()
tartaruga.goto(dados[0])
tartaruga.down()

for ponto in dados[1:]:
tartaruga.goto(ponto)


def main612(ficheiro, num_pontos):
# Formação dos dados
pares = gera_pares(num_pontos)
cria_ficheiro(ficheiro,pares)
# Leitura dos dados
pares_tartaruga = le_ficheiro(ficheiro)
# Visualização
tartaruga= cTurtle.Turtle()
visualiza(tartaruga,pares_tartaruga)
tartaruga.exitOnClick()


Com a definição gera_pares fabricamos a lista de pares de inteiros, entre 1 e 6. Usamos listas por compreensão.

Criamos o ficheiro, escrevendo os dados linha a linha. Como não nos podemos esquecer que num ficheiro de texto tudo tem que ser do tipo cadeia de caracteres, temos que fazer a conversão dos tipos. Entre dois números colocamos uma tabulação, e, no final a mudança de linha.

A leitura do ficheiro é agora a operação inversa, não havendo muito a acrescentar, pois retoma programas já criados.

A visualização parte da lista das coordenadas e faz mover uma tartaruga na tela de acordo com esses valores.

O programa principal, isto é, aquele que vai ser chamado, denominado main612, limita-se a dividir em três partes o programa: geração dos números, leitura dos dados e visualização.

sábado, 14 de novembro de 2009

Problema 6.8

Este problema já apresenta alguma complexidade. É uma boa altura para deixar de lado o teclado e pensar primeiro na solução. Claramente o problema pode ser dividido em três fases . Numa primeira, lemos os dados do ficheiro. Estamos a admitir que em cada linha do ficheiro se encontram os valores das temperaturas de uma cidade. Obtidos os dados, entramos na segunda fase, e temos o problema mais complexo: calcular a temperatura máxima e mínima em cada mês. Os comandos de leitura dos dados os permitem extrair os dados por linha. Mas precisamos de os associar por coluna. Para os mais experientes em matemática, se tudo estivesse numa matriz, isto equivalia a fazer a transposta da matriz. Na prática é o que vamos fazer, pois os dados guardados estão na forma de uma lista da listas. Finalmente, na terceira e última fase, mostramos o resultado por recurso ao módulo matplotlib. Definido o plano, devemos começar a desenvolver cada uma das partes, usando, se necessário, a mesma ideia de decompor um problema um sub-problemas. Eis o (nosso) resultado.


import pylab

def temp_max_min(f_ent):
"""
Lê temperaturas mensais de várias cidades, calcula valores máximos e mínimos.
Mostra o resultado num gráfico.
"""
# lê dados
f_in = open(f_ent)
dados = []
cidade = f_in.readline()
while cidade != '':
dados.append([float(valor) for valor in cidade[:-1].split()])
cidade = f_in.readline()
# calcula máximo e mínimo
lista_valores_mes = zip(*dados)
maximos = [max(mes) for mes in lista_valores_mes]
minimos = [min(mes) for mes in lista_valores_mes]
# mostra resultados
pylab.figure(1)
absissa = range(1,13)
pylab.xlabel('Meses')
pylab.ylabel('Temperaturas')
pylab.title(r'$\mathrm{M\acute aximo\,e\,M\acute inimo}$')
pylab.text(8,22,'Max')
pylab.text(8,18,'Min')
pylab.plot(absissa,maximos,'r-o',absissa, minimos,'b-^')
pylab.show()


Podemos visualizar o resultado.




A primeira fase está implementada entre as linhas 8 e 14. Os dados são lidos linha a linha (linhas 11 e 14). Cada linha vê os seus elementos separados e guardados numa lista, na forma de números em vírgula flutuante (linha 13). Essa lista é por sua vez guardada no contentor definido na linha 10. Na linha 13 usamos listas definidas por compreensão. O seu significado é semelhante ao dos conjuntos em matemática: A é o conjunto dos elementos x que satisfazem a condição y. O código pode ser substituído por outro mais normal.


# por compreenção
res = [float(valor) for valor in cidade[:-1].split()]
# equivalente "normal"
res = []
for valor in cidade[:-1].split():
res.append(float(valor))


As listas por compreensão podem ser mais complexas. Desde logo, podemos ter uma condição de filtragem.


# por compreenção
res = [float(valor) for valor in cidade[:-1].split() if float(valor) > 0 ]
# equivalente "normal"
res = []
for valor in cidade[:-1].split():
if float(valor) > 0:
res.append(float(valor))


Podemos ter também uma lista por compreensão dentro de outra. Uma vez habituados a elas saberemos apreciar a sua concisão e clareza.

Na segunda fase manipulamos a lista de listas (linhas 15 a 18). Aqui é crucial o uso da operação zip(*args). Dado um número variável de dados funciona como um fecho éclair: junta o que está na mesma posição. Quando, em vez de darmos os argumentos separados, os damos dentro de uma lista, temos que fazer um pouco mais de ginástica e separar esses elementos. Graças ao modo como o zip está definido basta usar a marca * antes do nome da lista.


>>> x = [1,2,3]
>>> y = ['a','b','c']
>>> zip(x,y)
[(1, 'a'), (2, 'b'), (3, 'c')]
>>> tudo = [x, y]
>>> tudo
[[1, 2, 3], ['a', 'b', 'c']]
>>> zip(tudo)
[([1, 2, 3],), (['a', 'b', 'c'],)]
>>> zip(*tudo)
[(1, 'a'), (2, 'b'), (3, 'c')]
>>>


Mas precisamos mesmo do zip? Não, mas a solução seria mais trabalhosa!

>
# com zip
lista_valores_mes = zip(*dados)
#sem zip
lista_valores_mes = []
for indice_mes in range(12):
mes = []
for indice_cidade in range(len(dados)):
mes.append(dados[indice_cidade][indice_mes])
lista_valores_mes.append(mes)


As listas por compreensão vêm de novo em nosso auxílio para nos facilitar a vida, relativamente à obtenção dos valores máximos e mínimos. O leitor pode gerar código alternativo, caso não se sinta confortável com o uso das listas por compreensão. Com o tempo e a prática o à vontade virá!

Na terceira fase mostramos os dados (linhas 19 a 28). Não há muito a dizer. O comando plot faz o trabalho por nós. As outras coisas são basicamente cosmética.

Problema 6.6

Comecemos com uma solução possível.


def identifica_numeros(nome_fich):
"""
Identifica se um ficheiro tem números, e retorna o resultado numa lista
"""
f_in = open(nome_fich,'r')
resultado =[]
texto = f_in.read()
texto_pal = texto.split()
for pal in texto_pal:
if pal.isdigit():
resultado.append(int(pal))
f_in.close()
return resultado


Analisemos o código. Abrimos o ficheiro para leitura (linha 5). De seguida criamos um contentor para guardar o resultado (linha 6). Lemos todo o ficheiro e transformamos a longa cadeia de caracteres numa lista de cadeias de caracteres, ou seja palavras. O separador de palavras é o espaço em branco (linhas 7 e 8). Entramos depois num ciclo, onde analisamos palavra a palavra para determinar se estamos na presença de uma cadeia em que todos os seus caracteres são dígitos (linhas 9 a 11). Dentro do ciclo o teste é feito usando o método isdigit(). Nos casos afirmativos, convertemos para inteiro e guardamos no contentor. Fechamos o ficheiro (linha 12) e devolvemos o resultado final (linha 13). Analise as debilidades da solução. Por exemplo: funciona se se tratar de números em vírgula flutuante? Funciona de o número tiver agarrado a um caracter não numérico? Que soluções tem para as questões enunciadas? Sugestão: faça uma análise caracter a caracter em vez de palavra a palavra.

Problema 6.4

Na solução deste problema aplicamos algumas das ideias discutidas na solução do problema 6.2.


def ler_seleccao (nome_fich, pos_inicial, num_caract):
"""
ler um conjunto de caracteres de um ficheiro
"""
conteudo = open(nome_fich,'r')
pos = conteudo.seek(pos_inicial-1,0)
cont = conteudo.read(num_caract)
conteudo.close()
return cont

Depois de abrir o ficheiro para leitura, posicionamos a janela de acesso na posição inicial de leitura (linha 6). Lemos de seguida os caracteres pretendidos e guardamos o resultado. Finalmente, fechamos o ficheiro e devolvemos o resultado. Percebe porque é que no comando seek colocamos pos_inicial - 1? Teste a solução em condições limite: posição inicial negativa ou para além do fim do ficheiro. Lembre-se: testar um programa a sério, deve permitir que todos os casos significativos de entradas sejam testadas.

Problema 6.2

O problema 6.2 é muito simples.


def primeira_linha (nome_fich):
"""
le a primeira linha do ficheiro conforme e guardado
"""
conteudo = open(nome_fich,'r')
cont = conteudo.readline()
conteudo.close()
return cont

Abrimos o ficheiro para leitura, lemos uma linha (forçosamente a primeira) e guardamos o resultado, fechamos o ficheiro e, finalmente, devolvemos o resultado guardado.

Durante uma das aulas práticas alguém perguntou: e se fosse a terceira linha, ou outra qualquer? Foi uma questão pertinente, mas também neste caso a solução é trivial.


def le_linha_n(nome_fich,n):
"""
lê a n-ésima linha do ficheiro caso exista e mostra-a.
Assume n > 0.
"""
f_in = open(nome_fich, 'r')
for i in range(n-1):
f_in.readline()
linha = f_in.readline()
f_in.close()
return linha

Entre as habituais instruções de abertura e fecho do ficheiro, temos agora um ciclo para ler sem guardar as (n-1) primeiras linhas. Saídos do ciclo, lemos a linha seguinte (a n-ésima linha) e guardamos. No final, devolvemos o resultado. Esta forma de fazer está relacionada com o facto de um ficheiro ser um objecto de acesso sequencial e não de acesso directo, como é o caso das listas, por exemplo. Claro que podemos navegar pelo ficheiro, reposicionando a janela de acesso com a instrução seek(). Isso não invalida no entanto o que dissemos. A menos que soubéssemos a posição do primeiro caracter da linha n! Experimente a solução apresentada e veja como ela reage a linhas inexistentes.

terça-feira, 10 de novembro de 2009

Flutuantes rangeres...

Em tempos recentes, uma foi hoje, fui questionado sobre a existência de um comando tipo range que funcione com números em vírgula flutuante e com incrementos fraccionários. Pré definido não há, mas podemos nós fazê-lo. Mete ao barulho conceitos que não deram ainda e são bizarros, por isso o melhor é agarrarem-se aos vossos assentos.

Comecemos pela solução.


def float_range(n1,n2=None,n3=1.0):
"""
Range para funcionar com números em vírgula flutuante.
Pode ser chamado como:
float_range(n)
float_range(n1,n2)
float_range(n1,n2,n3)
O significado é o mesmo do range normal.
"""

if n2 == None:
n2 = float(n1)
n1 = 0.0
proximo = n1
while (n3 >= 0.0 and proximo <= n2) or (n3 < 0.0 and proximo >= n2):
yield proximo
proximo = proximo + n3

Código estranho, não e? Sobretudo aquela instrução yield. O programa que escrevemos produz um objecto do tipo gerador. Cada vez que lhe peço, isto é chamo o comando, dá-me o próximo elemento de uma dada sequência. Neste caso, o próximo número da sequência entre n1 e n2, com incrementos de n3. Além disso, os parâmetros formais da definição têm valores por defeito! Assim, funciona para os três casos que conhecemos. Executando o código:


print 'Forma geral'
for i in float_range(1.0, 2.6,0.3):
print i
print 'Forma geral inversa'
for i in float_range(2.6, 1.0,-0.3):
print i
print 'Forma Simples'
for i in float_range(4.3):
print i
print 'Forma intermédia'
for i in float_range(2.5,4.3):
print i


obtemos como resultado:

Forma geral
1.0
1.3
1.6
1.9
2.2
2.5
Forma geral inversa
2.6
2.3
2.0
1.7
1.4
1.1
Forma Simples
0.0
1.0
2.0
3.0
4.0
Forma intermédia
2.5
3.5


Como vemos podemos usar o novo comando em ciclos for. Mas, e se quisermos os elementos em bloco, numa lista por exemplo. Uma solução fácil é a seguinte:


def float_range_lista(n1,n2=None,n3=1.0):
"""
Baseia-se em float_range
"""
x = float_range(n1,n2,n3)
y = list(x)
return y

Experimente agora fazer:

print float_range_lista(1.0,2.6,0.3)


e veja o que acontece. Espero que não tenha pesadelos. Mas se quiser sonhar, tente usar este princípio para gerar os números da sequência de Fibonacci. Se não sabe o que é ... procure através do Google!

sábado, 7 de novembro de 2009

Problema 5.36




São rosas senhor... Controlar uma tartaruga e a sua caneta não é difícil. O problema neste caso, tem a ver mais com a capacidade para gera uma pétala geometricamente perfeita. O programa que se segue mostra como. Fica o aviso: se são conhecermos os comandos, claro que é muito difícil!


def petala(pos,angulo,tamanho, amplitude):
""" Desenha pétala em pos com inclinação angulo e dimensão tamanho."""
#prepara
cTurtle.up()
cTurtle.goto(pos)
cTurtle.setheading(angulo)
cTurtle.hideturtle()
raio = tamanho * math.sin(math.radians(amplitude)/2.0)
cTurtle.down()
# cor
cTurtle.colormode(255)
r=random.randint(0,255)
g=random.randint(0,255)
b=random.randint(0,255)
cTurtle.fillcolor(r,g,b)
# desenha
cTurtle.fill(True)
cTurtle.forward(tamanho)
cTurtle.setheading(cTurtle.heading() + amplitude/ 2.0)
cTurtle.circle(raio,180)
cTurtle.goto(pos)
cTurtle.fill(False)

Então como fizemos? Começamos por preparar a tartaruga, posicionando-a no sítio certo e com a devida inclinação (linhas 4 a 9). De seguida tratamos dos problemas de cor, gerando a dita aleatoriamente e indicando com queremos preencher o objecto gerado com a cor (linhas 10 a 15). Passamos por fim à fase de desenho (linhas 16 a 22). A pétala é construída com dois segmentos formando entre si o ângulo pedido, e um arco de circunferência de 180 graus a unir as suas extremidades afastadas. Atente-se na necessidade de reposicionar a direcção da tartaruga, antes de desenhar o arco, para que a pétala tenha uma forma simétrica.

Problema 5.27

Ordenar uma pauta pelo valor e não pela chave já é mais complexo. Uma solução possível é a seguinte.


import operator

def pauta_nota(dic):
""" Ordena a pauta pela nota."""
itens = dic.items()
pauta = sorted(itens,key=operator.itemgetter(1), reverse=True)
return pauta


Socorremo-nos do módulo operator, que nos disponibiliza um método para obter elementos particulares de uma estrutura. O programa começa por obter a lista dos tuplos, isto é, pares (chave:valor), armazenados no dicionário (linha 3). Sendo uma lista pode ser ordenada. Usamos depois (linha 4) a operação pré-definida do sistema, sorted com os vários campos instanciados. Como vamos quere as notas mais altas no inicio indicamos reverse=True. Com o método ittemgetter vamos buscar a segunda componente de cada para, ou seja a nota, e é este elemento que é usado nas comparações necessárias parta o ordenamento.

Problema 5.26

Os dicionários são objectos não ordenados. Por isso, sempre que a questão da ordem nos interessa, temos que usar pequenos artifícios. Um deles é passar os elementos para uma lista, ordenar a lista e mostrar os elementos na forma de lista.


def pauta_nomes(dic):
""" Constrói a pauta ordenada pelos nomes."""
nomes = dic.keys()
nomes.sort()
pauta= list()
for nome in nomes:
pauta.append([nome,dic[nome]])
return pauta


Uma vez mais o padrão acumulador persegue-nos. Na lista pauta vamos guardando os elementos completos do dicionário, ordenados pelo nome (que é a chave do dicionário):

Problema 5.18

O exemplo do euromilhões é bom para mostrar como podemos escrever código mais limpo, genérico e reutilizável. Comecemos com uma solução trivial.


def euro():
# Gera 5 numeros
num_sol=[]
for i in range(5):
num=randint(1,50)
while num in num_sol:
num=randint(1,50)
num_sol.append(num)
num_sol.sort()
# Gera 2 estrelas
est_sol=[]
for i in range(2):
num=randint(1,9)
while num in est_sol:
num=randint(1,9)
est_sol.append(num)
est_sol.sort()
return [num_sol, est_sol]


Se notarmos, a geração dos números e das estrelas obedece ao mesmo padrão. Daí a ideia que escrever um sub-programa de geração de números.

def ger_numeros(quantidade, inf, sup):
num_sol=[]
for i in range(quantidade):
num=randint(inf,sup)
while num in num_sol:
num=randint(inf,sup)
num_sol.append(num)
num_sol.sort()
return num_sol


Feito isto podemos re-escrever o código.

def euromilhoes():
# Gera 5 numeros
num_sol=gera_numeros(5,1,50)
# Gera 2 estrelas
est_sol=gera_numeros(2,1,9)
return [num_sol, est_sol]

Note-se que a definição gera_numeros não está agarrada ao problema do euro milhões podendo ser usada em situações em que nos peçam uma lista de números inteiros, todos diferentes, entre certos limites.

Problema 5.16

Este problema é mais difícil do que o anterior. Não sabemos quantos termos temos que somar, pelo que não faz sentido o ciclo for. Termos que recorrer a um ciclo while. Por outro lado, para sabermos o erro, temos que comparar duas somas, uma delas com mais um termo que a anterior. De tudo isto resulta a solução seguinte.


def harmonica_erro(erro):
soma = 0
denominador = 1.0
while True:
nova_soma = soma + 1.0/denominador
if nova_soma - soma > erro:
return nova_soma
soma = nova_soma
denominador = denominador + 1


Veja-se que o ciclo é controlado por uma condição sempre verdadeira. Mas termina, pois o erro vai sendo cada vez menor e por isso haverá um momento em que o comando return será executado. Agora temos que fabricar explicitamente o denominador para cada etapa do ciclo.

Problema 5.15

O problema do cálculo do valor da série harmónica conhecido o número de termos é trivial. Apresenta-mo-lo sem mais.


def serie_harmonica(n):
""" Calcula a série harmónica com n termos."""
soma = 0.0
for den in range(1,n+1):
soma = soma + (1.0/den)
return soma


O leitor tem obrigação de já estar habituado a este padrão: um contador que é actualizado dentro do ciclo for. Notar que usamos range(1,n+1), pois o denominador não pode ser 0, e temos que somar n termos. Atente-se que, neste caso o cilco é usado para contar e gerar os denominadores.

Rotações Altamente

Em post anterior referi um conjunto de princípios enunciados por George Polya e que nos podem ajudar a resolver problemas. Vamos ver se consigo exemplificar com um problema que nos vai interessar proximamente.

Admitamos que queremos implementar um programa para pegar numa imagem e rodá-la um certo número de graus. Como fazer? Se pensarmos um pouco chegamos à conclusão que uma imagem digital não é mais do que um conjunto de pontos, cada um designado por pixel - do inglês picture element, possuindo determinadas características. Quantos mais pixeis numa imagem, maior a sua resolução. Ter uma máquina fotográfica com 12 milhões de pixeis é melhor do que ter uma só com 1.2 Megapixeis. Estas questões no entanto não nos vão ocupar agora. O que nos interessa é discutir é saber como resolver o problema da rotação. Dito de outro modo: dado um ponto no espaço para onde é que ele vai parar quando lhe aplicamos uma rotação? Para ajudar um pequeno desenho.




E agora mãos à obra!
Comecemos então pelo princípio. e no princípio é a fase de compreender o problema. Qual é a incógnita? As novas coordenadas do ponto, depois da rotação. Na figura, os valores de (w,z). Quais são os dados? Uma vez mais é simples: as coordenadas iniciais do ponto ((x,y)) e o ângulo de rotação (Θ).

Passemos a um plano para resolver o problema. Várias são as questões que podemos colocar nesta fase. Admitamos que não nos conseguimos lembrar de nenhum problema semelhante já resolvido no passado e cuja solução pudéssemos adaptar. Acontece com frequência! Será que conseguimos relacionar a incógnita com os dados? Aqui aparece o método! Dos nossos conhecimentos de trignometria sabemos que as coordenadas de um ponto se podem relacionar com o seno e o coseno do ângulo que forma com a origem dos eixos de coordenadas. Assim podemos relacionar (w,z) com Θ2. Parece que não avançámos muito pois temos mais uma incógnita. Mas será mesmo assim? É que este ângulo é a soma dos outros dois (Θ e Θ1). O primeiro ... é dado! E o segundo? Bem, uma vez mais este relaciona-se com as coordenadas (x,y) através das funções seno e coseno. E pronto. Temos um plano para partir dos dados em direcção às incógnitas.

Vamos então à terceira fase: executar o plano. Vamos aos cálculos! Serão feitos no pressuposto de que a circunferência tem raio 1. Comecemos a relacionar coisas.




Agora vem o passo normalmente conhecido por eureka, e que aqui se resume a saber um pouco de trignometria. Exprimir o coseno de uma soma:




Ficamos apenas com a questão de exprimir Θ1 em função de (x,y). Nada que o nosso saber trignométrico não resolva:




Continuemos a juntar as peças do puzzle.




Ou ainda de outro modo:




Usando o mesmo raciocínio para Z teremos:




Quem souber um pouco de álgebra sabe que estas relações se podem colocar na forma matricial. Vamos a isso.



A última fase da resolução de problemas diz respeito à reflexão sobre o que fizemos. Uma das questões é a verificação do resultado. Tentemos com um ângulo de 90 graus. Neste caso o seno é 1 e o coseno 0. É só substituir e aplicar a um ponto qualquer.




Mas agora podemos desenvolver um programa para resolver o problema da rotação encarado como produto de uma matriz por um vector! É o que vem a seguir.


def prod_escalar(vect1, vect2):
"""
Produto escalr de dois vectores representados por listas.
"""
prod = [vect1[i] * vect2[i] for i in range(len(vect1))]
return sum(prod)

def prod_matriz_vector(mat,vec):
"""
Produto de uma matriz m x n por um vector 1 x n
"""
res = [prod_escalar(mat[i],vec) for i in range(len(mat))]
return res


Nesta solução duas notas. Primeiro, o facto de termos usado uma definição auxiliar que nos faz o produto escalar de dois vectores. Aplicou-se o princípio da construção descendente de programas, por camadas de abstracção. Segundo, recorremos às listas por compreensão, o que nos permitiu tornar o programa mais legível.

E pronto. Já está!

Mini Teste # 1 - Versão C

Mais uma solução ( a última!).

1. O que queremos dizer quando afirmamos que um operador, +, por exemplo, está sobrecarregado?

Resposta

Um operador diz-se sobrecarregado quando efectua diferentes operações em função do tipo dos objectos. No caso de + temos, por exemplo a operação de adição de números ou a de concatenação de cadeia de caracteres.


>>> 5 + 3
8
>>> ‘ab’ + +cd’
‘abcd’


2. Considere a seguinte sessão interactiva no interpretador de Python.


>>> import math
>>> x = sin(5)
Traceback (most recent call last):
File "<string>", line 1, in <fragment>
NameError: name 'sin' is not defined
>>>


Explique de modo sintético mas rigoroso o que aconteceu.

Resposta

Ao importar o módulo matemático com import math, apenas o nome math fica guardado no espaço de nomes. Assim a operação sin é desconhecida do sistema a menos que se diga que faz parte do módulo matemático. Para tal temos que prefixar o nome da operação com o nome do módulo, com mostra a listagem. Não o fazendo dá-se um NameError.


>>> import math
>>> x = math.sin(5)
>>>


3. O programa da listagem abaixo pretende resolver o problema de duplicar os elementos numa lista. Por exemplo o que se pretende é:


>>> duplica([1,2,3])
[1,1,2,2,3,3]
>>>

def duplica(lista):
copia = lista[:]
for indice in range(len(lista)):
copia.insert(indice + 1,lista[indice])
return copia



No entanto não funciona. Identifique o tipo do erro que ocorre explicando a sua razão. Como podia corrigir o erro, embora usando a mesma ideia?

Resposta

O erro ocorre porque o programador não teve em linha de conta que a lista vai crescendo à medida que se inserem elementos. Funciona bem só para o primeiro elemento. A solução passa por ter esse aspecto em consideração como se indica na listagem.


def duplica_bem(lista):
copia = lista[:]
for indice in range(len(lista)):
copia.insert(2*indice + 1,lista[indice])
return copia


4. Desenvolva um programa que, dados um elemento numérico e uma lista de números, determina quantos elementos da lista são menores do que o número. A listagem abaixo ilustra o que se pretende.


>>> # ---> Aqui o seu programa de nome conta_menores.
>>> conta_menores(5,[2,8,6,5,3,2])
3
>>>


Resposta


Solução mais simples. Padrão acumulador (nome conta) a funcionar como contador. Percorre a lista pelo conteúdo. Para cada elemento da lista faz o teste e, caso se verifique a condição de ser menor, actualiza o contador.


def conta_menores(elem, lista):
conta = 0
for val in lista:
if val < elem:
conta = conta + 1
return conta

Mini Teste # 1 - Versão B

Aqui vai então a solução.

1. Identifique de forma clara e sintética as semelhanças e as diferenças entre objectos mutáveis e objectos imutáveis. Apresente exemplos concretos.


Resposta


Todos os objectos têm identidade, valor e tipo (semelhança). No caso dos objectos mutáveis podemos mudar o valor sem alterar a identidade e nos imutáveis não (diferença).

2. Explique o que acontece de modo claro, sintético e rigoroso quando executa o comando:


>>> cad = ‘a’ * 3


A sua explicação deve incluir a visualização do espaço de nomes e do espaço de objectos depois de executado o comando indicado.


Resposta

A operação produto aplicada a uma cadeia de caracteres replica a cadeia o número de vezes dado pelo outro operando. Neste caso o resultado seria a cadeia de caracteres ‘aaa’. A figura ilustra o espaço de nomes e o espaço dos objectos nos quais o nome cad se associa ao objecto ‘aaa’ através da identidade deste.






3. O programa da listagem abaixo pretende devolver o resultado da inversão de uma lista. No entanto não funciona. Identifique o tipo do erro que ocorre explicando a sua razão. Como podia corrigir o erro, embora usando a mesma ideia?


def inverte(seq):
"""Inverte a sequência seq.Onde está o erro?"""
aux = seq[:]
for indice in range(len(seq)/2):
aux[indice] = aux[len(seq) - indice - 1]
aux[len(seq) - indice - 1] = aux[indice]
return aux


Resposta


O programa de inversão tem um erro básico. A ideia é fazer a inversão trocando os elementos a igual distância das extremidades. No entanto a operação de troca no interior do ciclo for está incorrecta pois ao colocar um elemento numa dada posição sem salvar primeiro o que lá estava, impede a sua ulterior recuperação. A solução correcta seria colocar no interior do ciclo for as três instruções:


temp = aux[indice]
aux[indice] = aux[len(seq) - indice - 1]
aux[len(seq) - indice - 1] = temp


4. Desenvolva um programa que dadas duas listas devolve uma terceira formada pelos elementos das primeiras dispostos de modo alternado. Começa com a primeira lista.. A listagem abaixo ilustra o que se pretende.


Desenvolva um programa que dadas duas listas devolve uma terceira formada pelos elementos das primeiras dispostos de modo alternado. Come\c ca com a primeira lista.. A listagem abaixo ilustra o que se pretende.


>>> l1 = [1,2,3]
>>> l2 = ['a','b','c']
>>> # ---> Aqui o seu programa de nome alterna.
>>> alterna(l1, l2)
[1,'a',2,'b',3,'c']
>>>


Resposta


Uma solução consiste em usar o padrão acumulador: numa lista de nome aux vamos acumulando os pares de valores, um da lista 1 e outro da lista 2. A lista é percorrida pelos índices.


def shuffle_b(lista1,lista2):
""" alterna os elementos das listas. Têm o mesmo comprimento.
Começa com a lista 1.
"""
aux = []
for indice in range(len(lista1)):
aux.append(lista1[indice])
aux.append(lista2[indice])
return aux

domingo, 1 de novembro de 2009

Caçar com gato

O exercício 5.8 pede-nos que baralhemos uma cadeia de caracteres. Usámos o método shuffle do módulo random. Mas e se não soubermos da sua existência? Caçamos com gato ... Este não é um problema fácil. Existem várias soluções, umas mais elegantes e eficientes do que outras. Como ainda não se falou de recursividade vamos mesmo ter que caçar com um gato muito ... rafeiro: a iteração. Eis uma solução para o problema de gerar permutações de elementos guardados numa lista.


def permuta_it(lista):
"""
Devolve as permutações de uma lista de elementos.
"""
resultado = [[]]
for i in range(len(lista)):
aux_1 = []
for elem in resultado:
aux_2 =[]
for j in range(len(elem) + 1):
aux_2.append(elem[:j] + [lista[i]] + elem[j:])
aux_1.extend(aux_2)
resultado = aux_1[:]
return resultado


Para chegarmos a esta solução baseámo-nos na ideia da construção indutiva da solução, método já referido em post anterior. A solução é construída etapa a etapa, de baixo para cima. Começando com uma lista vazia (linha 5), Entramos num ciclo (linhas 6 a 13), que será repetido tantas vezes quantos os elementos da nossa lista original. Dentro do ciclo, na primeira etapa, construímos todas as permutações de comprimento 1, com o primeiro elemento da lista original. Só há uma permutação! Depois, na etapa 2 do ciclo, pegamos nessa permutação e fabricamos todas as de comprimento 2, juntando o segundo elemento da lista original de todos os modos possíveis a cada uma das soluções da etapa anterior (linhas 7 a 12). Neste ficamos com as duas permutações de dois elementos. E assim sucessivamente, por cada etapa do ciclo, até termos usado todos os elementos da lista original. Vejamos dois exemplos:


>>> permuta_it([1,2,3])
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
>>> permuta_it(['r','a','m','o'])
[['o', 'm', 'a', 'r'], ['m', 'o', 'a', 'r'], ['m', 'a', 'o', 'r'], ['m', 'a', 'r', 'o'], ['o', 'a', 'm', 'r'], ['a', 'o', 'm', 'r'], ['a', 'm', 'o', 'r'], ['a', 'm', 'r', 'o'], ['o', 'a', 'r', 'm'], ['a', 'o', 'r', 'm'], ['a', 'r', 'o', 'm'], ['a', 'r', 'm', 'o'], ['o', 'm', 'r', 'a'], ['m', 'o', 'r', 'a'], ['m', 'r', 'o', 'a'], ['m', 'r', 'a', 'o'], ['o', 'r', 'm', 'a'], ['r', 'o', 'm', 'a'], ['r', 'm', 'o', 'a'], ['r', 'm', 'a', 'o'], ['o', 'r', 'a', 'm'], ['r', 'o', 'a', 'm'], ['r', 'a', 'o', 'm'], ['r', 'a', 'm', 'o']]
>>>