PHP查找所有组合

Question

I'm trying to find all possible combinations of a word, and have certain letters replaced.

So, I have the following code:

<form name="search" action="<?php echo $_SERVER['PHP_SELF']; ?>" method="post">
<input type="text" name="searchterm" />
<input type="submit" value="Submit"/>
</form>

<?php


function pset($array) {
    $results = array(array());

    foreach ($array as $element)
        foreach ($results as $combination)
            array_push($results, array_merge(array($element), $combination));

    return $results;

}


$searchterm = $_POST["searchterm"];

$search  = array(
                    array("t","7"),
                    array("e","3")
                );



$searchpowerset=pset($search);                 

foreach($searchpowerset as $a)
{
    $newterm = str_replace($a[0][0],$a[0][1],$searchterm);
    echo $newterm . "<br/>";
}


?>

The input for this from the form would be: peter

I would expect the output to include:

p3t3r
p373r

At the moment it's returning:

peter
pe7er
p3t3r
p3t3r

The repetitons aren't an issue as I can get rid of those easily, but I need to be able to have all replacements work on each cycle through.

Thanks in advance.

Answer 1

Your code substitutes every instance of a character in the string, so it can't really work.

My implementation:

$searchterm = $_POST['searchterm'];

$search = array( array('e', '3'), array('t', '7'), array('e', 'E') );

function replace($string, $prefix = '')
{
    global $search;

    // If $string is empty, we've reached the last character,
    // so there is only one permutation. In that case, return it.
    if(!$string) return array($prefix);

    // Otherwise, take the first character in a string,
    // then prepend it to all found combinations of the rest.
    $result = array();
    $letter = substr($string, 0, 1); // <- first character (head of $string)
    $rest   = substr($string,1);     // <- next characters (tail of $string)

    // Find all combinations of $rest (with $prefix and $letter
    // prepended to them), then add them to the $result array.
    $result = array_merge($result, replace($rest, $prefix . $letter));
    foreach($search as $term) {
        // In case the current $letter can be substituted by something in
        // $search, repeat the last step with the replaced character
        // instead of $letter.
        if($term[0] == $letter) {
            $result = array_merge($result, replace($rest, $prefix . $term[1]));
        }
    }

    return $result;
}

var_dump(replace($searchterm));

Since the function has to return all combinations, it recursively calls itself for both the original character, and every replaced one.

Now, why does it work at all? For each call, one character moves from $string to $prefix. This character is the first character of the $string, or it's substituted value. If there are substituted values, results are returned both for the original and modified one. When there is no more characters to move, it returns the $prefix which now contains the whole string.

So, for the string 'pet', the call tree would look like this:

[$string, $prefix]
                                     ->['', 'pe7']
                                     |
['pet', '']->['et', 'p']->['t', 'pe']->['', 'pet']
                        |
                        ->['t', 'p3']->['', 'p3t']
                                     |
                                     ->['', 'p37']

And from that, you can clearly see the combinations: 'pe7', 'pet', 'p3t', 'p37' (though the order would be different, but that's not important).