PHP查找所有组合

Question

我试图找到一个单词的所有可能的组合，并且取代了某些字母。

所以，我有以下代码：

<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/>"; 
} 


?> 

从形式对此的投入将是：彼得

我期望的输出包括：

p3t3r 
p373r 

在它返回的那一刻：

peter 
pe7er 
p3t3r 
p3t3r 

重复不是问题，因为我可以很容易地摆脱这些问题，但是我需要能够在每个周期都有所有替换工作。

在此先感谢。

Answer 1

你的代码会替换字符串中每个字符的实例，所以它不能真正起作用。

我的实现：

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

由于函数必须返回所有组合，它递归调用自身针对原始字符，每一个取代。

现在，为什么它可以工作？对于每次调用，一个字符从$ string移动到$前缀。这个字符是$ string的第一个字符，或者它是替代值。如果有替换值，则返回原始结果和修改结果的结果。当没有更多字符要移动时，它返回$前缀，该前缀现在包含整个字符串。

所以，对于字符串“宠物”，调用树是这样的：

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

，并从，你可以清楚地看到组合：“PE7”，“宠物”，“P3T” ，'p37'（虽然顺序会有所不同，但这并不重要）。

Answer 2

我看到你的代码是基于如下所示O'Reilly的PHP食谱：http://docstore.mik.ua/orelly/webprog/pcook/ch04_25.htm

我想有在分选到一维数组作为按字母顺序排列的字符串所有可能的字符组合的列表。我们将O'Reilly代码更改为以下运行良好的代码。

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

组合数组现在包含字母的所有可能组合的字母顺序列表。

对于我们的应用程序，我们有一个单词数据库表，其中还包含一个字母字母顺序的单词列。我们将这个输出结果与我们的拼字游戏数据库进行匹配，从而制作出一个漂亮的拼字游戏字词生成器。

对于输出中看到的一个例子：http://scrabblehints.com