CODEWITHSUNDEEP
phpcombinatorics
Ok_
Ok_

Reputation: 33

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 substitutes? In this example, "a" can be replaced to both "b" and "c", so strings include:

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

Upvotes: 3

Views: 1049

Answers (4)

Janus Troelsen
Janus Troelsen

Reputation: 21300

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

Upvotes: 0

Joost
Joost

Reputation: 10413

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.

Upvotes: 2

Karoly Horvath
Karoly Horvath

Reputation: 96266

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

Upvotes: 0

Dmitrii Tarasov
Dmitrii Tarasov

Reputation: 414

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

Upvotes: 2

Related Questions