Golf Programming: permutazioni
Questa volta Eineki ci propone un quiz classico che però presenta sempre interessanti spunti: le permutazioni.
Ecco la mia soluzione, sono 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.uniqPer questa soluzione mi sono inspirato ad una bellissima funzione scritta in Erlang:
permutation([]) -> [[]];
permutation(L) -> [[H|T] || H <- L, T <- permutation(L--[H])].Vediamo un pò di orientarci con questa particolare sintassi: Erlang utilizza dei pattern per descrivere quale ‘versione’ della funzione utilizzare, in questo caso abbiamo due ‘permutation’, una che si attiva quando il parametro è una lista vuota e una quando non lo è.
Concentriamoci quindi sulla seconda riga: il nome del costrutto che stiamo osservando si chiama ‘List Comprehension‘ ed il suo funzionamento è tutto basato nell’eseguire l’operazione a sinistra del doppio pipe ‘||’ utilizzando i valori specificati nella parte destra.
Quindi nel nostro caso stiamo costruendo una lista di liste; notiamo infatti che a sinistra del doppio pipe risiede il costrutto classico di lista in Erlang: [H|T] ( H stà per Head e rappresenta il primo elemento della lista, T per tail e indica i rimanenti elementi della lista). Ma come vogliamo che sia costruita ognuna di queste liste ? La risposta è nella parte destra del List Comprehension:
- In H si alterneranno tutti gli elementi di L
- In T, per ogni elemento di L, si alterneranno le liste derivanti dal calcolo delle permutazioni sulla lista L privata dell’elemento che è in H.
In queste sede mi sono limitato ad una veloce overview sul funzionamento della funzione ‘permutation’ in Erlang; per chi intenedesse approfondire la tematica consiglio vivamente questo articolo di Peter Miller che riesce a illustrare in modo molto comprensibile quanto io qui ho solo sommariamente spiegato.
Tags: Erlang, Golf Programming, Permutazioni, Tail Recursion