[Rio-pm] Novo Golf

Fernando Oliveira fernandocorrea em gmail.com
Quinta Junho 19 17:37:43 PDT 2008


Eu não quero uma solução p/ isso, eu quero tacadas!
Golf não é p/ ser rápido, é p/ ser pequeno...

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
>



-- 
Just another Perl Hacker,
Fernando (SmokeMachine)
http://perl-e.org
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: http://mail.pm.org/pipermail/rio-pm/attachments/20080619/9d64b2aa/attachment.html 


Mais detalhes sobre a lista de discussão Rio-pm