Golf Programming: permutazioni

golf, linguaggi 1 Minutes

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:

  1. Scrivere un programma, il più breve possibile, che risolva il problema enunciato prima e riportato meglio qui sotto;
  2. per ogni linguaggio utilizzato è considerato vincitore il programma scritto usando meno caratteri;
  3. l’efficienza dell’algoritmo non è un fattore fondamentale ma il programma deve terminare senza errori;
  4. si può optare, se più concisa, per una funzione, piuttosto che un programma intero;
  5. 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.

Pubblicato da Eineki

Pubblicato

8 pensieri riguardo “Golf Programming: permutazioni”

  1. 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.uniq

    per 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

  2. 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.uniq

    Domani ci rifletto…

    Edit: mi sono permesso di aggiungere un ritorno a capo per problemi di impaginazione – Eineki

  5. 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)

  6. 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])));

  7. 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.uniq

    Yez !
    Edit: mi sono permesso di aggiungere un ritorno a capo per problemi di impaginazione – Eineki

  8. Pingback: Permutazioni, Golf Programming, Erlang, Tail Recursion | Flying memes

Lascia un commento