Декодирование анаграммы с рекурсивной функцией не дает ожидаемого результата

<?php

function anagram($string, $wordlist)
{
if(empty($string))
return;

foreach($wordlist as $line)
{
$line = $org = trim($line);
$line = str_split($line);
sort($line);

foreach($line as $key => $value)
{
if($value != $string[$key])
{
continue 2;
}
}

echo $org . anagram(array_slice($string, count($line)), $wordlist);
}

echo PHP_EOL;

}$string = "iamaweakishspeller";
$string = str_split($string);
sort($string);

$file = file('wordlist');

anagram($string, $file);

У вас есть словарь (файл) и анаграмма, которая содержит одно или несколько слов. Анаграмма не содержит знаков препинания или букв в оригинальном слове.

Теперь вы хотите найти все истинные решения, в которых вы используете все символы анаграммы и расшифровываете их в слова из словаря.

Замечания: Существует вероятность, что вы найдете несколько решений, и вы никогда не узнаете, каким было исходный текст и в каком порядке были слова, так как символы нескольких слов смешаны в анаграмме, и у вас нет знаков препинания или случая буквы в нем.

Ваш код

Проблема в вашем текущем коде состоит в том, что вы смешали несколько слов. Если вы сортируете их сейчас и хотите найти их в словаре, вы не сможете их найти, так как символы нескольких слов смешаны. Пример:

anagram  = "oatdgc"  //"cat" + "dog"wordList = ["cat", "dog"]wordListSorted    = ["act", "dgo"]
anagramSorted     = acdgot
↓↓↓
WordListSorted[0] → cat   ✗ no match
WordListSorted[1] → dog   ✗ no match

---

Сначала я объясню теоретически, как мы строим все возможные истинные решения, а затем объясню, как работает каждая часть кода.

теория

Итак, для начала у нас есть анаграмма и словарь. Теперь мы сначала фильтруем словарь по анаграмме и сохраняем только те слова, которые могут быть построены по анаграмме.

Затем мы просматриваем все слова и для каждого слова добавляем его в возможное решение, удаляем его из анаграммы, фильтруем словарь по новой анаграмме и рекурсивно вызываем функцию с новыми значениями.

Мы делаем это до тех пор, пока анаграмма не станет пустой и мы не найдем истинное решение, которое добавляем в нашу коллекцию решений, или пока не останется слов, и это не будет возможным решением.

Код

У нас есть две вспомогательные функции array_diff_once() а также preSelectWords() в нашем коде.

array_diff_once() почти так же, как встроенный array_diff() функция, за исключением того, что она удаляет значения только один раз, а не все вхождения. В противном случае не так много, чтобы объяснить. Он просто перебирает второй массив и удаляет значения один раз в первом массиве, который затем возвращается.

function array_diff_once($arrayOne, $arrayTwo){
foreach($arrayTwo as $v) {
if(($key = array_search($v, $arrayOne)) !== FALSE)
array_splice($arrayOne, $key, 1);
}

return $arrayOne;

}

preSelectWords() принимает анаграмму и список слов в качестве аргумента. Он просто проверяет с помощью array_diff_once(), какие слова из списка слов могут быть построены с данной анаграммой. Затем он возвращает все возможные слова из списка слов, который можно построить с помощью анаграммы.

function preSelectWords($anagram, $wordList){
$tmp = [];
foreach($wordList as $word){
if(!array_diff_once(str_split(strtolower($word)), $anagram))
$tmp[] = $word;
}

return $tmp;

}

Теперь к основной функции decodeAnagram(), Мы передаем анаграмму и список слов, которые мы сначала фильтруем preSelectWords()в качестве аргументов функции.

В самой функции мы в основном просто перебираем слова и для каждого слова удаляем его из анаграммы, фильтруем список слов по новой анаграмме, добавляем слово в возможное решение и вызываем функцию рекурсивно.

Мы делаем это до тех пор, пока либо анаграмма не станет пустой, и мы не найдем истинное решение, которое мы добавляем в наш массив решений, либо пока в списке не останется слов и с этим не будет никакого возможного решения.

function decodeAnagram($anagram, $wordList, $solution, &$solutions = []){

if(empty($anagram) && sort($solution) && !isset($solutions[$key = implode($solution)])){
$solutions[$key] = $solution;
return;
}

foreach($wordList as $word)
decodeAnagram(array_diff_once($anagram, str_split(strtolower($word))), preSelectWords(array_diff_once($anagram, str_split(strtolower($word))), $wordList), array_merge($solution, [$word]), $solutions);

}

Код

<?php

function decodeAnagram($anagram, $wordList, $solution, &$solutions = []){

if(empty($anagram) && sort($solution) && !isset($solutions[$key = implode($solution)])){
$solutions[$key] = $solution;
return;
}

foreach($wordList as $word)
decodeAnagram(array_diff_once($anagram, str_split(strtolower($word))), preSelectWords(array_diff_once($anagram, str_split(strtolower($word))), $wordList), array_merge($solution, [$word]), $solutions);

}

function preSelectWords($anagram, $wordList){
$tmp = [];
foreach($wordList as $word){
if(!array_diff_once(str_split(strtolower($word)), $anagram))
$tmp[] = $word;
}

return $tmp;

}

function array_diff_once($arrayOne, $arrayTwo){
foreach($arrayTwo as $v) {
if(($key = array_search($v, $arrayOne)) !== FALSE)
array_splice($arrayOne, $key, 1);
}

return $arrayOne;

}$solutions = [];
$anagram = "aaaeeehiikllmprssw";
$wordList = ["I", "am", "a", "weakish", "speller", "William", "Shakespeare", "other", "words", "as", "well"];
//↑ file("wordlist", FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES)

decodeAnagram(str_split(strtolower($anagram)), preSelectWords(str_split(strtolower($anagram)), $wordList), [], $solutions);
print_r($solutions);?>

Выход

Array
(
[Iaamspellerweakish] => Array
(
[0] => I
[1] => a
[2] => am
[3] => speller
[4] => weakish
)

[ShakespeareWilliam] => Array
(
[0] => Shakespeare
[1] => William
)

)

_{(Игнорируйте ключи здесь, так как это идентификаторы решений)}