How to get all possible string permutations with PHP?

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 开发者_如何学JAVAsubstitutes? In this example, "a" can be replaced to both "b" and "c", so strings include:

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

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.

$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) );

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

<?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);
?>