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.

Grindelia

What you want are called "permutations", not "combinations". – Itinerate

@Itinerate I don't think Johan meant combination in the mathematical sense. But yes, you are right. – Copula

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. – Callas

@Felix: I know. But it helps to use the right term when Googling a solution. – Itinerate

All answers here that suggest backtracking/recursion for this are wrong. See here #2530008 – Cultivator

@Stereofrog: What is wrong in using recursion for this problem? Sure there are several approaches to solve this and the wiki link suggested by you is one of them. – Oscar

Answer 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

Oscar

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 – Redingote

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

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

Answer 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?

Lx

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

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? – Insensibility

@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. – Lx

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.. – Bibliophage

Answer 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.

Equality

Answer 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");

Statant

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

Answer 5

I made a simple class that uses Generators to create the permutations.This way you can just iterate over all possible combinations without exhausting the memory.

The class can take either a string or an array, and returns a Generator object which can be iterated over with foreach.

Obviously the longer the string or array, the longer it takes to generate all the permutations.

This has been build against PHP 7.4

class Permutation {

    /** @var string|array **/
    protected $permutationRoot;
    protected int $permutationLength;

    /**
     * @param $permutationRoot
     */
    protected function __construct( $permutationRoot ) {
        $this->permutationRoot = $permutationRoot;
        $this->permutationLength = is_array($permutationRoot)
            ? count($permutationRoot)
            : strlen($permutationRoot);
    }

    /**
     * @param string|array $permutationRoot
     *
     * @return \Generator
     */
    public static function resolve( $permutationRoot ): \Generator
    {
        $instance = new static($permutationRoot);

        return $instance->backTrack(
            $instance->permutationRoot,
            0,
             $instance->permutationLength,
         );
    }

    /**
     * @param string|array $permutation
     * @param int $index
     * @param int $length
     *
     * @return \Generator
     */
    protected function backTrack($permutation, int $index, int $length): \Generator
    {
        if ($index === $length) {
            yield $permutation;
        }

        for ($i = $index; $i < $length; $i++) {
            $this->swap($permutation, $index, $i);
            yield from $this->backTrack($permutation, $index + 1, $length);
            $this->swap($permutation, $index, $i); // backtrack.
        }
    }

    /**
     * @param $permutation
     * @param int $index
     * @param int $n
     *
     * @return void
     */
    protected function swap(&$permutation, int $index, int $n): void {
        $temp = $permutation[$index];
        $permutation[$index] = $permutation[$n];
        $permutation[$n] = $temp;
    }
}

// Test
foreach ( Permutation::resolve('hey') as $perm ) {
    echo $perm . "\n";
}

Forswear

Answer 6

$sentence = "This is a cat";
$words = explode(" ", $sentence);
$num_words = count($words);
$uniqueWords = [];
for ($i = 0; $i < $num_words; $i++) {
    for ($j = $i; $j < $num_words; $j++) {
        $uniqueWord = '';
        for ($k = $i; $k <= $j; $k++) {
            $uniqueWord .= $words[$k] . ' ';
        }
        $uniqueWords[] = trim($uniqueWord);
    }
}

var_dump($uniqueWords);

This worked for me

Deadening