Experimentalia

Appunti raminghi

Golf Programming: permutazioni

with 8 comments

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.

Written by Eineki

giugno 16, 2009 a 12:15 pm

8 Risposte

Subscribe to comments with RSS.

  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

    Sandro Paganotti

    giugno 16, 2009 at 23:34 pm

  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

    Sandro Paganotti

    giugno 17, 2009 at 0:03 am

  3. Non si tratta di preveggenza ma di pura invidia😉

    eineki

    giugno 17, 2009 at 0:42 am

  4. Scusate..ma gli spazi valgono come caratteri da conteggio?? (??)

    Kaig

    giugno 18, 2009 at 21:40 pm

  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)

    eineki

    giugno 18, 2009 at 22:41 pm

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

    eineki

    giugno 23, 2009 at 1:54 am

  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

    Sandro Paganotti

    giugno 25, 2009 at 22:27 pm

  8. […] volta Eineki ci propone un quiz classico che però presenta sempre interessanti spunti: le permutazioni.Ecco la mia soluzione, sono 100 […]


Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: