How to get all possible string permutations with PHP?

Question

There is a mapping of characters, like so:

$replacements = array(
 array('a', 'b'), // a => b
 array('a', 'c'), // a => c
 array('b', 'n'),
 array('c', 'x'),
);

And there is an input string, say "cbaa". How can I get all combinations, where at least one character is replaced to one of its substitutes? In this example, "a" can be replaced to both "b" and "c", so strings include:

xbaa
cnaa
xbba
cbca
cbab
cbac
...
xnaa
xnac
...

• Ok_: no, this is not homework
• Janus Troelsen: it should be pretty trivial to customize these answers: stackoverflow.com/questions/2617055/…

Answer 1

Here is an altered version of the code of Dmitry Tarasov (all credits to him please) which seems to be working properly.

class Combine {
 private static $_result = array();
 public static function run($str, $replacements){
 self::_run($str, $replacements, 0);
 return array_values(array_unique(self::$_result));
 }
 private static function _run($str, $replacements, $start){
 self::$_result[] = $str;
 for($i = $start, $l = strlen($str); $i < $l; $i++){ 
 self::_run($str, $replacements, $i+1); 
 if(isset($replacements[$str[$i]])){
 foreach($replacements[$str[$i]] as $key => $val){
 $str[$i] = $val;
 // call recursion
 self::_run($str, $replacements, $i+1);
 }
 }
 }
 }
}
print_r( Combine::run($str, $replacements) );

The private function was introduced to avoid those heavy array operations to be executed multiple times, while they're not used anywhere but from the root-call.

Answer 2

$replacements = array(
 array('a', 'b'), // a => b
 array('a', 'c'), // a => c
 array('b', 'n'),
 array('c', 'x'),
);
$str = 'cbaa';
// lets change replacements format
$replacementsSorted = array();
foreach ($replacements as $pair) {
 if (isset($replacementsSorted[$pair[0]])) {
 $replacementsSorted[$pair[0]][] = $pair[1];
 } else {
 $replacementsSorted[$pair[0]] = array($pair[1]);
 }
}
$replacements = $replacementsSorted;
class Combine {
 private static $_result = array();
 static function run($str, $replacements, $start) {
 self::$_result[] = $str;
 $l = strlen($str);
 for ($i = $start; $i < $l; $i++) { 
 if (isset($replacements[$str[$i]])) {
 foreach ($replacements[$str[$i]] as $key => $val) {
 $str[$i] = $val;
 if (in_array($str, self::$_result)) {
 continue;
 }
 // call recursion
 self::run($str, $replacements, $i+1);
 }
 }
 }
 return self::$_result;
 }
}
var_dump( Combine::run($str, $replacements, 0) );

• Ok_: Thanks, Dmitry, but it gives 9 results, 8 of which start with "x", which is wrong. Is it the same to you?
• Dmitrii Tarasov: Ok_, yep, you have right. Comment above from Joost fix my code

Answer 3

function combi($str, $replac, &$result, $builtstr="", $pos=0) {
 $len = strlen($str);
 if ($pos == $len) {
 if ($builtstr != $str)
 $result[] = $builtstr;
 return;
 }
 $c = $str[$pos];
 $poss = array();
 $poss[] = $c;
 foreach($replac as $v) {
 if ($v[0] == $c)
 $poss[] = $v[1];
 }
 foreach($poss as $k=>$c_repl) {
 combi($str, $replac, $result, $builtstr . $c_repl, $pos+1);
 }
}
$combinations = array();
combi("cbaa", $replacements, $combinations);

Answer 4

<?php
error_reporting(E_ALL | E_STRICT);
$replacements = array(
array('a', 'b'), // a => b
array('a', 'c'), // a => c
array('b', 'n'),
array('c', 'x'),
);
$inputstr = "cbaa";
$hash = array(); // hash map maps originals characters with an array of the original character and the other replacements
foreach ($replacements as $pair) {
 if (!isset($hash[$pair[0]])) { $hash[$pair[0]] = array($pair[0]); }
 $hash[$pair[0]][] = $pair[1];
}
echo "hash:\n";
print_r($hash);
$to_flat = array_map(function($c) use ($hash) { // maps original input string characters to an array of candidates
 return $hash[$c];
}, str_split($inputstr));
echo "to_flat:\n";
print_r($to_flat);
$perms = array_reduce($to_flat, function($akku, $letter_targets){
 $theseperms = array();
 foreach ($akku as $work) { // for each permutation made
 foreach ($letter_targets as $target) { // for each character candidate
 $newakku = $work;
 $newakku .= $target;
 $theseperms[] = $newakku;
 }
 }
 return $theseperms;
}, array(""));
unset($perms[array_search($inputstr, $perms, true)]); //remove cbaa
$perms = array_values($perms); //reset keys
echo "perms:\n";
print_r($perms);
?>