Take the 2-minute tour ×

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.

share|improve this question
What you want are called "permutations", not "combinations". –  Thomas Apr 11 '10 at 12:58
@Thomas I don't think Johan meant combination in the mathematical sense. But yes, you are right. –  Felix Apr 11 '10 at 13:03
Also consider, that you'll get n! results. For an input string of length 12 (no duplicate characters), that's about 480 million results, requiring about 5 GB of memory. –  Chris Lercher Apr 11 '10 at 13:05
@Felix: I know. But it helps to use the right term when Googling a solution. –  Thomas Apr 11 '10 at 13:27
All answers here that suggest backtracking/recursion for this are wrong. See here stackoverflow.com/questions/2529508/… –  user187291 Apr 11 '10 at 14:26
show 1 more comment

4 Answers

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.

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

share|improve this answer
Downvoter, please explain your position –  zavg Sep 18 '13 at 15:25
I don't think this deserves a downvote. –  Christian Mark Nov 29 '13 at 1:50
add comment

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.


$input = "hey";

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

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

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


Prints out:

    [0] => h
    [1] => e
    [2] => y
    [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.

share|improve this answer
add comment

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++) {
          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.


#php a.php
share|improve this answer
@Downvoter: Care to explain ? –  codaddict Apr 11 '10 at 14:50
add comment

I'd say this is a typical backtracking problem.

share|improve this answer
add comment

Your Answer


