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

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.