Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to generate all permutations of a string in PHP?

I need an algorithm that return all possible combination of all characters in one string.

I've tried:

$langd = strlen($input);  for($i = 0;$i < $langd; $i++){      $tempStrang = NULL;      $tempStrang .= substr($input, $i, 1);   for($j = $i+1, $k=0; $k < $langd; $k++, $j++){    if($j > $langd) $j = 0;    $tempStrang .= substr($input, $j, 1);  }  $myarray[] = $tempStrang; } 

But that only returns the same amount combination as the length of the string.

Say the $input = "hey", the result would be: hey, hye, eyh, ehy, yhe, yeh.

like image 973
Johan Avatar asked Apr 11 '10 12:04

Johan


People also ask

How do you print all possible combinations of a string in Python?

In Python, we can use the built-in module itertools to get permutations of elements in the list using the permutations() function. However, we can also write your utility function to generate all permutations of a string. We can do this either recursively or iteratively.


1 Answers

You can use a back tracking based approach to systematically generate all the permutations:

// function to generate and print all N! permutations of $str. (N = strlen($str)). function permute($str,$i,$n) {    if ($i == $n)        print "$str\n";    else {         for ($j = $i; $j < $n; $j++) {           swap($str,$i,$j);           permute($str, $i+1, $n);           swap($str,$i,$j); // backtrack.        }    } }  // function to swap the char at pos $i and $j of $str. function swap(&$str,$i,$j) {     $temp = $str[$i];     $str[$i] = $str[$j];     $str[$j] = $temp; }     $str = "hey"; permute($str,0,strlen($str)); // call the function. 

Output:

#php a.php hey hye ehy eyh yeh yhe 
like image 197
codaddict Avatar answered Oct 18 '22 00:10

codaddict