Anagramma di stringhe

[tidusuper91]

Salve,
sto cercando di implementare una funzione che mi faccia un'anagramma di una stringa data.

Ecco quello che sono riuscito a "ideare":

I Passo:
Trasformare la stringa in un array contenente le sue lettere:

function array_string ($string) {


    for($i=0;$i<(strlen($string));$i++) {
    
    $a_string[$i] = substr($string, $i, 1);




}


return $a_string;

} 

II Passo:

Una permutazione di una stringa (ex. abcd) è uguale ad un array contenente:

Perm(abcd) = array (


 [0] => a . Perm(bcd),
 [1] => b . Perm(cda),
 [3] => c . Perm(dab),
 [4] => d . Perm(abc)

);

//E a sua volta 

Perm(bcd) = array (


 [0] => b . Perm(cd),
 [1] => c . Perm(db),
 [3] => d . Perm(bc)


);

// Analogo per Perm(cda), Perm(dab),Perm(abc)

// Ancora poi

Perm(cd) = array (
    [0] => c . Perm(d) // Che equivale a cd
    [1]=> d . Perm(c) // Che equivale a dc
); 

[...].

E' evidente che serva una funzione

Perm(); 

ricorsiva. Ma non so come implementarla, una mano?

[satifal]

Dai un'occhiata QUI ci sono ben tre algoritmi per le permutazioni.

[tidusuper91]

Li avevo già visti. Quegli algoritmi stampano a schermo la giusta permutazione.
Io avrei bisogno di avere tutte le permutazioni in un array multidimensionale!

[satifal]

Non capisco quale sia il problema?!?! Invece di stamparli a video li inserisci in un array multidimensionale!!!

[Santino83_02]

invece degli echo e dei print ti metti il risultato in un array e te lo fai ritornare. l'array di storage lo passerai come puntatore alla funzione di permutazione che sceglierai

EDIT:

se ho ben capito dagli esempi:

function Fuchs_perm($buf,&$output){
  $res = implode("",$buf);
  $output[] = $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);
      $output[] = $res;
      $p[$i]++;
      $i=1;
   } else {
      $p[$i] = 0;
      $i++;
   }
  }
}


$buffer = array('p','a','r','o','l','a');
$output = array();

Fuchs_perm($buffer,$output);

print_r($output); 

[tidusuper91]

Originariamente inviato da Santino83_02
invece degli echo e dei print ti metti il risultato in un array e te lo fai ritornare. l'array di storage lo passerai come puntatore alla funzione di permutazione che sceglierai

EDIT:

se ho ben capito dagli esempi:

function Fuchs_perm($buf,&$output){
  $res = implode("",$buf);
  $output[] = $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);
      $output[] = $res;
      $p[$i]++;
      $i=1;
   } else {
      $p[$i] = 0;
      $i++;
   }
  }
}


$buffer = array('p','a','r','o','l','a');
$output = array();

Fuchs_perm($buffer,$output);

print_r($output); 

Ok. Appena ho tempo lo provo. Riusciresti a scrivermi, anche in pseudocode, cosa fa quell'algoritmo? Nel senso, a livello di operazioni PHP riesco a capire ma non riesco a capire il filo logico del Fuchs algorithm. In particolare non capisco questo:

 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);
      $output[] = $res;
      $p[$i]++;
      $i=1;
   } else {
      $p[$i] = 0;
      $i++;
   } 

Grazie e scusate il disturbo!

[oly1982]

... forse nn ho capito lo scopo... ma
http://it.php.net/manual/en/function.str-shuffle.php

[tidusuper91]

Originariamente inviato da oly1982
... forse nn ho capito lo scopo... ma
http://it.php.net/manual/en/function.str-shuffle.php

Avevo già visto la funzione shuffle. Ma io ho bisogno di stampare tutti gli anagrammi di una stringa, non solo 1. =)

Penso che l'algoritmo Fuchs sia il migliore a livello di prestazioni, vorrei però capirlo. Magari se qualcuno riesce a scrivermi un diagramma o uno pseudocode...

[Santino83_02]

guarda cercavo online non ho trovato molto apparte questo:

http://permute.tchs.info/01example.php

cmq quel codice serve per fare le permutazioni senza ricorrere alla ricorsione, quindi immagino che l'array $p serva a questo. Ora però non ho tempo di mettermi a scrivere lo pseudocode dell'algoritmo.