How to generate all permutations of a string in PHP?

Question

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.

Solution 1

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

Solution 2

My variant (works as well with array or string input)

function permute($arg) {
    $array = is_string($arg) ? str_split($arg) : $arg;
    if(1 === count($array))
        return $array;
    $result = array();
    foreach($array as $key => $item)
        foreach(permute(array_diff_key($array, array($key => $item))) as $p)
            $result[] = $item . $p;
    return $result;
}

P.S.: Downvoter, please explain your position. This code uses additional str_split and array_diff_key standard functions, but this code snippet is the smallest, it implements pure tail recursion with just one input parameter and it is isomorphic to the input data type.

Maybe it will lose benchmarks a little when comparing with other implementations (but performance is actually almost the same as in @codaddict's answer for several character strings), but why we can't we just consider it as one of the different alternatives which has its own advantages?

Solution 3

I would put all the characters in an array, and write a recursive function that will 'stripe out' all the remaining characters. If the array is empty, to a reference passed array.

<?php

$input = "hey";

function string_getpermutations($prefix, $characters, &$permutations)
{
    if (count($characters) == 1)
        $permutations[] = $prefix . array_pop($characters);
    else
    {
        for ($i = 0; $i < count($characters); $i++)
        {
            $tmp = $characters;
            unset($tmp[$i]);

            string_getpermutations($prefix . $characters[$i], array_values($tmp), $permutations);
        }
    }
}
$characters = array();
for ($i = 0; $i < strlen($input); $i++)
    $characters[] = $input[$i];
$permutations = array();

print_r($characters);
string_getpermutations("", $characters, $permutations);

print_r($permutations);

Prints out:

Array
(
    [0] => h
    [1] => e
    [2] => y
)
Array
(
    [0] => hey
    [1] => hye
    [2] => ehy
    [3] => eyh
    [4] => yhe
    [5] => yeh
)

Ah yes, combinations = order doens't matter. permutations = order does matter.

So hey, hye yeh are all the same combination, but 3 separate permutations as mentioned. Watch out that the scale of items goes up very fast. It's called factorial, and is written like 6! = 6*5*4*3*2*1 = 720 items (for a 6 character string). A 10 character string will be 10! = 3628800 permutations already, which is a very big array. In this example it's 3! = 3*2*1 = 6.

Solution 4

My approach uses recursion and no loops, please check and give feedback:

function permute($str,$index=0,$count=0)
{
    if($count == strlen($str)-$index)
        return;

    $str = rotate($str,$index);

    if($index==strlen($str)-2)//reached to the end, print it
    {
        echo $str."<br> ";//or keep it in an array
    }

    permute($str,$index+1);//rotate its children

    permute($str,$index,$count+1);//rotate itself
}

function rotate($str,$index)
{
    $tmp = $str[$index];
    $i=$index;
    for($i=$index+1;$i<strlen($str);$i++)
    {
        $str[$i-1] = $str[$i];
    }
    $str[$i-1] = $tmp;
    return $str;
}
permute("hey");

View more solutions

Comments

[Ben]

If there a multiple occurrences of a letter within $arg, permutations in $result aren't unique.

[Ben]

Depends on the solution. ;-) Didn't want to offend you nor decry your solution. Wasn't sure, if this is well known. What would you suggest to filter the redundant permutations out?

[zavg]

@ben I mean that other solutions in answers to this question are the same (from the point of view of uniqueness of values). In your case you can use, for example, array_unique standard function to filter repeating values.

[Lucabro]

I'm not sure to understand why there's a second swap... i've tried to execute without and the solution are the same only in a little bit different order

[Daniel Omine]

The "filter" to guarantee unique combinations, don't need be applied inside this function. The purpose of this function is permute the characters, regardless of duplicated combinations. If wish unique combinations, create another routine to apply the filters before execute this one..

[Asif Iqbal]

please see the link: englishact.com/Permutation/index.php?permutation=abb#result

[atfergus]

This solution does not work with a string containing only a single character.

[Shurvir Mori]

Yes, I agree @AsifIqbal , try with aa . technically it has to show only aa. but here it shows aa aa.