K. Redmyer K. Redmyer - 21 days ago 8
PHP Question

Find all possible permutations from a given set for specific string indices (PHP)

I have been racking my brain at this for a few days and I seem to be stuck. I'm new to PHP so please forgive any sloppiness or errors.

Given a pattern, for example something like an email address "ab@?b?.ca" I need to replace any instance of '?' with all possible permutations from a set of characters 'a-e', '@', and '.'

This is what I have right now:

function permute($str, $ch, $i, $n, &$output) {
if ($i == $n) {
array_push($output, $str);
} else {
for ($x = $i; $x < $n; $x++) {
for ($y = 0; $y < count($ch); $y++) {
$str[$x] = $ch[$y];
permute($str, $ch, $i + 1, $n, $output);
}
}
}
}

# each ? in the pattern to be replaced by all possible permutations of characters in chars array
# a through e as well as @ and .
$output = array();
$chars = range('a', 'e');
array_push($chars, '@');
array_push($chars, '.');

# the pattern to be checked
$pattern = "ab@?b?.ca";
permute($pattern, $chars, 0, strlen($pattern), $output);


... which is very close to what I want, but not quite correct. The function operates on every character of the string, but it should only do the work on the '?'s. Is there something else I can do that I'm missing? I will respond in a comment and edit if I figure this out!

Answer

Here is my working solution:

function permute($str, $arr, $i, $n, &$result) {
    $nLen = strlen($n);
    // cycle through every position of needle
    while (($i = strpos($str, $n, $i)) !== false) {
        $i = $i + $nLen;
        // cycle through each replacement value
        foreach ($arr as $value) {
            $modified = substr_replace($str, $value, $i - $nLen, $nLen);
            // if there are no needles left, save it
            if (stristr($modified, $n) === false) {
                $result[] = $modified;
            }
            permute($modified, $arr, $i, $n, $result);
        }
    }
}

# each ? in the pattern to be replaced by all possible permutations of characters in chars array
# a through e as well as @ and .
$chars = range('a', 'e');
array_push($chars, '@');
array_push($chars, '.');

# the pattern to be checked
$pattern = "ab@?b?.ca";
$result = array();
$needle = '?';
$index = 0;

permute($pattern, $chars, $index, $needle, $result);
var_dump($result);

This assumes that you only want to save values in which no needles remain. For example, instead of:

array(63) {
  [0]=>
  string(9) "ab@ab?.ca"
  [1]=>
  string(9) "ab@aba.ca"
  [2]=>
  string(9) "ab@abb.ca"
  // etc...

It will output:

array(49) {
  [0]=>
  string(9) "ab@aba.ca"
  [1]=>
  string(9) "ab@abb.ca"
  [2]=>
  string(9) "ab@abc.ca"
  // etc...

If you do in fact want the first result, then simply remove the stristr($modified, $n) === false conditional.