[Rio-pm] Novo Golf

[Nuba Princigalli]

Fernando,

From: "Fernando Oliveira" <fernandocorrea at 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