sexta-feira, 8 de novembro de 2013

Aleatoriedades (I)

Cada vez mais tomamos consciência que muito dos acontecimentos que nos rodeiam têm uma natureza probabilística. Os valores possíveis para um evento aleatório dá origem a uma distribuição de probabilidades. Existem vários tipos de distribuições, e.g., normal, uniforme, poisson. Para podermos simular esses processos precisamos de ser capazes amostrar essas distribuições. Em Python o módulo random ajuda-nos nessa tarefa. Por exemplo, o método randint gera um inteiro dentro de um intervalo de acordo com uma distribuição uniforme. Já o método random (não confundir com o nome do módulo...) permite obter um real no intervalo [0,1), ainda de acordo com uma distribuição uniforme. Na realidade os números são pseudo-aleatórios mas isso é outra história. Vamos olhar para algumas aplicações muito simples.

Admitamos que nos pedem para gerar uma sequência com n números inteiros todos no intervalo [a,b]. Em função do que sabemos, o mais natural é gerar os números um a um e ir guardando o resultado no único contentor que já conhecemos (em breve, tomaremos conhecimento com outros...). Claramente, do que foi dito estamos perante um padrão de programação do tipo ciclo - acumulador. Daí o código:
def gera_tuplos_n(n,a,b):
    """Gera um tuplo com n inteiros entre a e b."""
    res = () # <-- o acumulador
    for i in range(n): # <-- o ciclo
        # gera número
        num = random.randint(a,b)
        # guarda número
        res += (num,)
    return res
Admitamos que o enunciado é ligeiramente alterado impondo que os números devem ser todos distintos. Aparentemente a solução é fácil e envolve mudar ligeiramente o código anterior por forma que dentro do ciclo, depois de gerar um elemento, se teste se ele já pertence ou não à nossa sequência, só o introduzindo no caso de não pertencer.
def gera_tuplos_n(n,a,b):
    """Gera um tuplo com n inteiros distintos entre a e b."""
    res = ()
    for i in range(n):
        num = random.randint(a,b)
        if num not in res:
             res += (num,)
    return res
Mas se executarmos o código temos uma surpresa: o tuplo tem em geral menos elementos do que os pedidos. Um minuto de reflexão permite identificar o problema: quer o elemento seja introduzido ou não no tuplo, o contador interno do ciclo for é sempre incrementado. Solução? Simples: passar para um ciclo while que é executado enquanto não tivermos os n elementos desejados:
def gera_tuplos_n_diff(n,a,b):
    """Gera um tuplo com n inteiros entre a e b, todos diferentes"""
    res = ()
    i = 0
    while i < n:
        num = random.randint(a,b)
        if num not in res:
            res += (num,)
            i += 1
    return res
E já está. Mesmo sendo um programa muito simples ainda há lugar a pequenas melhorias. Como dissemos o ciclo é executado enquanto não tivermos n elementos no tuplo. então porque não usar o comprimento do tuplo como critério de saída???
def gera_tuplos_n_diff(n,a,b):
    """Gera um tuplo com n inteiros entre a e b, todos diferentes"""
    res = ()
    while len(res) < n:
        num = random.randint(a,b)
        if num not in res:
            res += (num,)
    return res
Agora sim, estamos satisfeitos. Vamos experimentar, por exemplo com:
print(gera_tuplos_n_diff(10, 5,10))
Mas algo de estranho acontece: o programa não apresenta nenhum resultado! Pensando de novo, lá encontramos a razão: queremos dez números distintos quando no intervalo entre 5 e 10 só existem 6!! Nada que não se possa precaver por recurso a uma asserção:
def gera_tuplos_n_diff_b(n,a,b):
    """Gera um tuplo com n inteiros entre a e b, todos diferentes"""
    assert n <= (b-a+1),'Um...números a menos para o tamanho do tuplo.'
    res = ()
    while len(res) < n:
        num = random.randint(a,b)
        if num not in res:
            res += (num,)
    return res
Já estou a ouvir alguns de vocês: mas porque é tanta trabalheira, não bastava.... Sim claro, temos um método que nos permite gerar os n números distintos só com uma instrução:
def gera_tuplos_n_diff(n, a,b):
    """Gera um tuplo com n inteiros entre a e b, todos diferentes"""
    assert n <= (b-a+1),'Um...números a menos para o tamanho do tuplo.'
    return random.sample(range(a,b+1),n)
Mas se executar o programa verá que o contentor usado não é um tuplo, mas sim uma lista de que ainda não falámos. Fica a informação...

Já agora: se em vez de inteiros fossem números reais então os métodos a usar seriam o random, para o intervalo [0,1), ou o uniform, para o intervalo [a,b]. Mas o resto não se alterava.

E agora sim, deste já nos livrámos.

Vamos passar para outro tipo de problema. E se em vez de números nos pedem para fabricar aleatoriamente uma sequência de ADN. Como sabemos este tipo de sequência pode ser representado por uma cadeia de caracteres em que os valores possíveis para cada posição é uma de entre as quatro bases, ‘A, ‘T’, ‘C’, e ‘G’. Mas tirando esse aspecto o problema do ponto de vista informático segue o mesmo padrão do problema anterior: ciclo + acumulador. A única questão a resolver prende-se com a geração das bases. Mas para isso temos o método choice!
def gera_adn(n):
    """Gera uma cadeia de ADN de comprimento n."""
    adn = ''
    for i in range(n):
        base = random.choice('ATCG')
        adn += base
    return adn
Simples, não é? E se nos disserem que a probabilidade da Adenina (‘A’) é dupla das restantes bases? Não tem problema: incluímos duas ocorrências de ‘A’ na cadeia que o método choice vai usar para a escolha:
def gera_adn(n):
    """Gera uma cadeia de ADN de comprimento n."""
    adn = ''
    for i in range(n):
        base = random.choice('AATCG') <-- dois As!!
        adn += base
    return adn
Por fim pensemos numa tartaruga muito libertária que adora passear ao acaso, podendo deslocar-se apenas para norte (‘N’), sul (‘S’), este (‘E’) ou oeste (‘O’). Como gerar um percurso que a tartaruga tem que percorrer? Bom, não me diga que ainda tem dúvidas... ciclo + acumulador!
def gera_tarta(n):
    """Gera uma sequência de n movimentos aleatórios de uma tartaruga."""
    tarta = ''
    for i in range(n):
        passo = random.choice('NSEO')
        tarta += passo
    return tarta
E já agora vamos passear!
def passeio_tarta(posx, posy, tam_passo,cor,caminho):
    """Simula o caminha da tartaruga num espaço reticulado."""
    # inicializa
    turtle.showturtle()
    turtle.pencolor(cor)
    turtle.fillcolor(cor)
    turtle.shape('turtle')
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # passeia
    for comando in caminho:
        if comando == 'N':
            turtle.setheading(90)
            turtle.forward(tam_passo)
        elif comando == 'S':
            turtle.setheading(270)
            turtle.forward(tam_passo) 
        elif comando == 'E':
            turtle.setheading(0)
            turtle.forward(tam_passo) 
        elif comando == 'O':
            turtle.setheading(180)
            turtle.forward(tam_passo)
        else:
            # Ignorar
            continue
    turtle.hideturtle()
    
def main_tarta(n, posx,posy,tam_passo,cor):
    caminho = gera_tarta(n)
    passeio_tarta(posx,posy,tam_passo,cor,caminho)
O nosso programa main decompõe o problema em dois sub-problemas. Primeiro gera o caminho e depois é que simula o passeio. Simular o passeio envolve simplesmente um ciclo que interpreta cada letra do caminho como um comando a executar.

Podemos agora brincar um pouco. Por exemplo, admitir que a nossa tartaruga privilegia ir para oeste e para norte:
def gera_tarta(n):
    """Gera uma sequência de n movimentos aleatórios de uma tartaruga."""
    tarta = ''
    for i in range(n):
        passo = random.choice('NNNSEOOO')
        tarta += passo
    return tarta
Ou então que o comprimento do passo é maior para norte e para este e menor para sul e para oeste.
def passeio_tarta(posx, posy, tam_passo,cor,caminho):
    """Simula o caminha da tartaruga num espaço reticulado."""
    # inicializa
    turtle.showturtle()
    turtle.pencolor(cor)
    turtle.fillcolor(cor)
    turtle.shape('turtle')
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # passeia
    for comando in caminho:
        if comando == 'N':
            turtle.setheading(90)
            turtle.forward(tam_passo)
        elif comando == 'S':
            turtle.setheading(270)
            turtle.forward(0.5*tam_passo) 
        elif comando == 'E':
            turtle.setheading(0)
            turtle.forward(tam_passo) 
        elif comando == 'O':
            turtle.setheading(180)
            turtle.forward(0.5*tam_passo)
        else:
            # Ignorar
            continue
    turtle.hideturtle()
Ou ainda podemos colorir o passo em função da orientação e admitir comandos inválidos (no caso 'X').
def gera_tarta(n):
    """Gera uma sequência de n movimentos aleatórios de uma tartaruga."""
    tarta = ''
    for i in range(n):
        passo = random.choice('NNNSXEOOO') # <-- um X
        tarta += passo
    return tarta

def passeio_tarta(posx, posy, tam_passo,cor,caminho):
    """Simula o caminha da tartaruga num espaço reticulado."""
    # inicializa
    turtle.showturtle()
    turtle.fillcolor(cor)
    turtle.shape('turtle')
    turtle.penup()
    turtle.goto(posx, posy)
    turtle.pendown()
    # passeia
    for comando in caminho:
        if comando == 'N':
            turtle.pencolor('red')
            turtle.setheading(90)
            turtle.forward(tam_passo)
        elif comando == 'S':
            turtle.pencolor('green')
            turtle.setheading(270)
            turtle.forward(tam_passo) 
        elif comando == 'E':
            turtle.pencolor('blue')
            turtle.setheading(0)
            turtle.forward(tam_passo) 
        elif comando == 'O':
            turtle.pencolor('yellow')
            turtle.setheading(180)
            turtle.forward(tam_passo)
        else:
            # Ignorar
            turtle.pencolor('black')
            turtle.dot(6)
            continue
    turtle.hideturtle()
E mais todas as variantes que quiser imaginar...

Sem comentários:

Enviar um comentário