-+  Associazione
-+  Documenti
-+  Eventi
-+  Community
-+  Blog
-+  Link

Ottobre 2013

Dom Lun Mar Mer Gio Ven Sab
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

Cerca






 

« That's Amore | Home | De comparatione »

Permutazioni e Perl
04.06.04

L'altro giorno dree sul canale ci parlava della sua intenzione di assemblare un modulo scritto in C per fare le permutazioni. Subito incuriosito, non avendo fatto studi matematici particolari, (sono un ragioniere :) ho chiesto alla mia fidanzata (laurea scienze statistiche) cos'erano le permutazioni, e come al solito sono entrato in loop!.

Nel caso specifico dree parlava di permutazioni con ripetizione cioe' vale a dire, dati 'n' elementi trovare tutte le loro combinazioni con una lunghezza pari a 'x' posizioni:

Es.
elementi: a b c
posizioni: 2
risultato: ba ca ab cb ac bc

Dopo innumerevoli paturnie mentali, la soluzione che ho trovato e che vi volevo presentare sfrutta il sistema con il quale si conta normalmente, in qualsiasi base numerica (binaria, ottale , decimale etc).

Infatti se noi immaginiamo che a,b,c corrispondono alle unita' numeriche e vogliamo "contare" sostituendo queste lettere ai numeri avremmo:

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
etc

ovviamente essendo gli elementi "tre" avremo un sistema a base 3 quindi le soluzioni ottenibili nel caso di 2 posizioni sono 3^2 + 3^1 cioe' 12.

Su questo principio ho scritto poche righe di codice che "contassero", sostituendo i numeri ai caratteri della stringa che viene passata come parametro.

Lanciato il programma la prima volta pero' mi accorsi subito che c'era qualcosa che non andava. Infatti come per i numeri alcune "unita'" venivano ovviamente ripetute.

Osservando infatti l'esempio sopra riportato, vi sono "aa" "bb" etc casi non richiesti dal problema. Non e' stato difficile pero' individuare queste eccezioni e saltare il ciclo senza considerarle.

I matematici mi scuseranno se ho utilizzato nomenclature matematiche in modo inappropriato. Immagino che esista un metodo scientifico apposito per calcolare le permutazioni, ma volevo comunque riportavi la mia soluzione.

Lanciare lo script passando come primo parametro la stringa e come secondo le posizioni.

#! /usr/bin/perl
$p[$i++]=$_ for split //,$ARGV[0];
until ($n[$ARGV[1]])
 {
  $n[0]++; $r="";
  for (0..$ARGV[1]-1)
   {
    if ($n[$_]==$i) { $n[$_]=0; $n[$_+1]++;}
    $r.= ($n[$_]?$n[$_]:"0").":";
   }
  if ($r!~ /(\d+)\:.*\1/)
   {
    print $p["$_"] for split /\:/,$r;
    print "\t";
   }
 }

Inviato da LucaS il 04.06.04 19:09
Ti è piaciuto questo articolo? Iscriviti al feed!

D:
Sull'autore...
D:
La ML di Perl.it
Iscriviti! mongers@lists.perl.it è la lista ufficiale di Perl Mongers Italia per porre quesiti di tipo tecnico, per rimanere aggiornato su meeting, incontri, manifestazioni e novità su Perl.it.
D:
Annunci Google