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 в $.Этот символ является первым символом строки $ или его замещенным значением.Если есть замещенные значения, результаты возвращаются как для исходного, так и для модифицированного.Когда больше нет символов для перемещения, он возвращает префикс $, который теперь содержит всю строку.

Итак, для строки 'pet' дерево вызовов будет выглядеть так:

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

И из этого вы можете ясно увидеть комбинации: «pe7», «pet», «p3t», «p37» (хотя порядок будет другим, но это не важно).

Answer 2

Я вижу, что ваш код основан на поваренной книге PHP O'Reilly, показанной здесь: http://docstore.mik.ua/orelly/webprog/pcook/ch04_25.htm

Я хотел получить список всех возможных комбинаций символов, отсортированных в одномерный массив в виде строк в алфавитном порядке. Мы изменили код О'Рейли на следующий, который работал хорошо.

 $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