permutazioni

Una definizione abbastanza intuitiva delle permutazioni potrebbe essere: “Le permutazioni semplici di n elementi distinti sono tutti i diversi gruppi che si possono formare con gli elementi dati, che rispettino le seguenti clausole:

1. Ogni gruppo deve essere composto da n elementi.
2. Un elemento non può essere duplicato in un gruppo.
3. Due gruppi sono distinti quando differiscono solo per l’ordine con cui sono disposti gli elementi.

La matematica, in particolare il calcolo combinatorio ci insegna che tutte le possibili combinazioni di n elementi sono n!. Per fare un esempio, tutte le possibili permutazioni delle lettere che compongono la parola “mare“, sono 4!, ovvero 4*3*2*1 = 24.
In questo caso, e in tutti i casi in cui tutte le lettere che compongono una certa parola sono distinte, le permutazioni equivalgono agli anagrammi. Nel caso in cui vi siano lettere ripetute, il numero di anagrammi sarà minore. Ad esempio gli anagrammi della parola “olio” sono 4! / 2! = 12

L’implementazione non è banale, ma di algoritmi per la risoluzione del problema “permutazioni” ce ne sono parecchi anche perché l’argomento è quasi sempre presente nei programmi di studio ad indirizzo informatico, quindi è inutile scervellarsi, basta cercarli e cercare di capire la logica con la quale sono stati composti. Cosa più interessante, invece è cercare quello più efficiente.

Per la comparazione ho scelto tre degli algoritmi più noti e comuni, due di essi utilizzano la ricorsione mentre il terzo no. Normalmente il linguaggio con cui vengono presentati questi algoritmi è il C, oppure uno pseudocodice, quindi ho provveduto ad effettuare la traduzione in PHP.

Il primo algoritmo preso in considerazione è quello ricorsivo tradizionale, forse il più conosciuto, tratto da “Appunti di informatica libera” capitolo 595.4 (Algoritmi tradizionali) Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Funzione ricorsiva
function Perm($lista, $k, $m) {
  if ($k == $m){
    $parola = "";
    for ($i=0; $i<=$m; $i++){
      $parola .= $lista[$i];
    }
  echo ($parola."
");
  }
  else{
    for ($i=$k; $i<=$m; $i++){
      $tmp = $lista[$k];
      $lista[$k] = $lista[$i];
      $lista[$i] = $tmp;
      Perm($lista, $k+1, $m);          
      $tmp = $lista[$k];
      $lista[$k] = $lista[$i];
      $lista[$i] = $tmp;
    }
  }   
}

Il secondo preso in esame, sempre ricorsivo, è pubblicato negli “user contribs” del manuale PHP. Si tratta di una versione modificata da alejandro dot garza at itesm dot mx di un algoritmo presentato su uno dei libri del noto editore O’Reilly. Sebbene non sia efficientissimo in termini di prestazioni, si tratta comunque di un esempio interessante per chi programma in PHP, in quanto utilizza alcune funzioni native del linguaggio. Ho commentato le istruzioni per la restituzione del risultato in un array, perché sebbene comodo, lo avrebbe penalizzato eccessivamente.
Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function array_2D_permute($items, $perms = array( )) {
//static $permuted_array;
    if (empty($items)) {
        //$permuted_array[]=$perms;
        //print_r($new);
      print join('', $perms) . "
";
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             array_2D_permute($newitems, $newperms);
         }
         //return $permuted_array;
    }
}

Infine un algoritmo non ricorsivo ideato da Phillip Paul Fuchs, il riferimento è: Scalable Permutations, in particolare ho tradotto in PHP l’esempio descritto in The Counting QuickPerm Algorithm. Phillip Paul Fuchs è un vero esperto di queste tematiche e ha scritto anche un libro sull’argomento. Non a caso, dunque, il suo algoritmo risulta il più efficiente!
Ecco il codice:

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

function Fuchs_perm($buf){
  $res = implode("",$buf);
  echo("$res
");
  $string_length = count($buf);
  for($i=0;$i<$string_length;$i++){
    $p[$i]=0;
  }
  $i=1;
  while($i < $string_length){
   if ($p[$i] < $i) {
      $j = $i % 2 * $p[$i];
      $tmp=$buf[$j];
      $buf[$j]=$buf[$i];
      $buf[$i]=$tmp;
      $res = implode("",$buf);
      echo("$res
");
      $p[$i]++;
      $i=1;
   } else {
      $p[$i] = 0;
      $i++;
   }
  }
}

Per testare la velocità di esecuzione ho utilizzato questa interessante classe PHP realizzata da Ioannis Cherouvim: A time measuring and performance benchmarking class, eliminando tutte le istruzioni di stampa dell’output. I risultati sono visibili nella seguente tabella e nel grafico all’inizio dell’articolo.

Se volete fare qualche test con questi 3 algoritmi potete scaricare questo pacchetto
E’ richiesto PHP versione 5.3.x o superiore!

Conclusioni:

I risultati parlano da soli e rispecchiano le mie aspettative. L’algoritmo di Fuchs, è nettamente migliore degli altri, altamente ottimizzato e non ricorsivo. Quelli ricorsivi soffrono degli svantaggi tipici di questa tecnica: ogni chiamata ricorsiva consuma memoria ed utilizza un salto ad una funzione che produce un inevitabile rallentamento.