Golf Programming: permutazioni
Proseguiamo con il golf programming con un nuovo problema da risolvere.
Anche questa volta si tratta di un classico (anche se programmarlo secondo le regole del golf me lo ha fatto vedere sotto una nuova luce).
Le Regole
Per che non le ricordasse, e per chi comincia da questa puntata a seguire la rubrica, riporto le regole:
- Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
- per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno caratteri;
- l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
- si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
- ovviamente non di vince niente se non la soddisfazione di aver accettato una sfida ed averla vinta.
L’algoritmo
L’algoritmo da implementare deve, data una stringa, calcolare tutte le sue possibili permutazioni.
Al solito, un esempio servirà a chiarire tutto meglio di una descrizione formale:
data in input la stringa abc, il programma deve stampare, le stringhe abc, acb, bac, bca, cab e cba.
Ovviamente l’ordine delle stringhe restituite non è importante mentre lo è non riportare ripetizioni: la stringa aba, ad esempio, deve dare come risultato solamente aba, aab e baa.
A parte i soliti rubysti che avranno sicuramente un costrutto nel linguaggio tipo .permuta secondo me si tratta di una sfida stimolante, specie per chi volesse risolverla in ricorsione. Come le altre volte, posterò la mia soluzione nel prossimo fine settimana. Buona sfida.
Ciao, sono il solito rubyista
Questa è la mia soluzione, sono 114 caratteri:
p (a=proc{|l,n|l.empty? ? "#{n}" : l.map{|s|a.call(l-[s], n+[s])}}).call((ARGV[0]||"a").split(//),[]).flatten.uniqper provarlo basta copiarlo in un file ‘.rb’ e lanciarlo:
ruby perm.rb abc
ps: certo che hai del profetico
http://www.ruby-doc.org/core-1.9/classes/Array.html#M002019
Edit: mi sono permesso di aggiungere un ritorno a capo per problemi di impaginazione – Eineki
Sandro Paganotti
Giugno 16, 2009 alle 23:34 pm
Oops, piccolo bug che mi ha (temporaneamente) obbligato a far salire il codice a 135 caratteri.
p (a=proc{|l,n|l.empty? ? "#{n}" : l.map{|s|a.call(l.to_s.sub(s,'').split(//), n+[s])}}).call((ARGV[0]||"a").split(//),[]).flatten.uniqDomani ci rifletto…
Edit: mi sono permesso di aggiungere un ritorno a capo per problemi di impaginazione – Eineki
Sandro Paganotti
Giugno 17, 2009 alle 0:03 am
Non si tratta di preveggenza ma di pura invidia
eineki
Giugno 17, 2009 alle 0:42 am
Scusate..ma gli spazi valgono come caratteri da conteggio?? (??)
Kaig
Giugno 18, 2009 alle 21:40 pm
Quelli necessari al funzionamento del programma si (altrimenti potresti usare linguaggi come whitespace ).
Quelli utili solo all’indentazione no puoi anche eliminarli prima di postare o segnalarli come tali; ad esempio potresti scrivere qualcosa come (130/145)
eineki
Giugno 18, 2009 alle 22:41 pm
In ritardo, per un problema con evolution che sarà oggetto di un imminente post, la mia soluzione, in php, conta 178 caratteri.
function p($a,$r=”){$x=array();$a[0]||$x[$r]=1;for(;$a[$i++];$l=substr($a,1),$x=array_merge(p($ l,$r.$a[0]),$x),$a=$l.$a[0]);return $x;}echo join(‘,’,array_keys(p($argv[1])));
eineki
Giugno 23, 2009 alle 1:54 am
Ciao! Come promesso c’ho riflettuto e sono riuscito a portare il tutto a 100 caratteri !
def k(l,n);l==''?n:l.split(//).map{|s|k(l.sub(s,''),n+s)}end; p k((ARGV[0]||"abcd"),'').flatten.uniqYez !
Edit: mi sono permesso di aggiungere un ritorno a capo per problemi di impaginazione – Eineki
Sandro Paganotti
Giugno 25, 2009 alle 22:27 pm
[...] volta Eineki ci propone un quiz classico che però presenta sempre interessanti spunti: le permutazioni.Ecco la mia soluzione, sono 100 [...]
Permutazioni, Golf Programming, Erlang, Tail Recursion | Flying memes
Giugno 28, 2009 alle 11:27 am