PHP Find All Combinations

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(
  开发者_StackOverflow                  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.

---

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

---

I see your code is based on the O'Reilly PHP Cookbook shown here: http://docstore.mik.ua/orelly/webprog/pcook/ch04_25.htm

I wanted to have a list of all possible combinations of characters sorted in to a single dimensional array as alphabetized strings. We altered the O'Reilly code to the following that worked well.

 $lettersArray = array('C', 'A', 'T', 'D', 'O', 'G', 'S');

//Create a tiered results array of all possible combinations of letters
 $results = array(array());
 foreach ($lettersArray as $element) {
     foreach ($results as $combination) {
         array_push($results, array_merge(array($element), $combination));
     }
 }

 //Build combinations array by compacting results array and sorting the letters in to alphabetical order
 $combinations = array();
 foreach ($results as $result){
     sort($result);
     $string = implode($result);
     array_push($combinations, $string);
 }
 sort($combinations);

The combinations array now contains an alphabetized ordered list of all possible combinations of letters.

For our app, we then have a database table of words that also contains a column with the word with the letters alphabetized. We take this output and match it against our database of scrabble words to make a nifty scrabble word builder.

For an example of the output see: http://scrabblehints.com