[Rio-pm] Novo Golf

[Samir Cury]

pra quem quiser arriscar, tem o módulo Math::Combinatorics , que calcula
fatorial ou direto a combinação, de um jeito mais chatinho, usei ele uma vez
pra calcular o tempo que eu levaria pra (o que chamo de bruteforce perfeito)
numa chave WPA de 8 caracteres, para minha surpresa deu próximo de um
século, numa máquina com um Athlon 64 X2 ou seja, quem usa WPA pode dormir
sossegado até onde sei, parando de fugir do tema, fica a dica do módulo,
ainda não curto golfe não, mas qq dia desses começo.

abs!

2008/6/19 Nuba Princigalli <nuba em fastmail.fm>:

> Fernando,
>
> From: "Fernando Oliveira" <fernandocorrea em gmail.com>
>
>> e queria fazer algo, que lembra a tão famosa "torre de hanoi". para que
>> seja
>> exibido todas as combinações possiveis...
>>
>> jose jorge pereira sandro joao
>> jose pereira sandro joao jorge
>> jose
>> jose pereira
>> sandro jose
>> ....
>>
>> Alguem entendeu a idéia?* "
>>
>
> As duas primeiras linhas sao duas permutacoes de uma mesma combinacao. Ja
> as
> duas ultimas sao exemplos de combinacoes, dois a dois, do subconjunto.
>
> O golf vai ser gerar todas as permutacoes de todas as combinacoes
> possiveis?
>
> Esse tipo de problema cresce (ou melhor, explode) muito rapido em funcao do
> tamanho da entrada. A complexidade eh O(n!) onde n eh o tamanho da entrada.
> Isso eh soh pras permutacoes. O que voce quer eh a combinacao, i a i, de N
> elementos vezes o somatorio de N!, com i variando de 1 ate N. Pior ainda.
>
> Olha aqui http://en.wikipedia.org/wiki/Factorial
>
> A torre de hanoi, que voce usou como exemplo, eh um problema que cresce
> rapido tambem. Nao eh fatorial, mas eh O(2^n).
>
> Se voce quiser uma solucao nao-golf mas que faca isso pro seu amigo,
> faca uma busca por "perl cookbook permute".
>
> Nuba
> _______________________________________________
> Rio-pm mailing list
> Rio-pm em pm.org
> http://mail.pm.org/mailman/listinfo/rio-pm
>
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: http://mail.pm.org/pipermail/rio-pm/attachments/20080619/3cc0ba3d/attachment.html