使用递归函数解码字谜不会给出预期的输出

Question

所以我正在尝试将字谜解码为字典文件中的单词。但是我的递归函数并不像我期望的那样运行。

关于代码的想法是消除字母，因为它们用于单词，并输出它产生的字符串。

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

这是我目前的结果，看起来很糟糕，但我的代码有一些问题 - 它会进入一个无限循环，单词列表中大约有 200 个单词。

有人可以在这上面加个高峰吗？

Answer 1

情况

你有一本字典（文件）和一个包含一个或多个单词的字谜。字谜不包含原始单词的任何标点符号或字母大小写。

现在你想找到所有真正的解决方案，你用尽了字谜的所有字符并将其解码为字典中的单词。

Note: There is a chance that you find multiple solutions and you will never know which one the original text was and in which order the words were, since the characters of multiple words are mixed in the anagram and you don't have punctuation or the case of the letters in it.

您的代码

您当前代码中的问题正是您将多个单词混合在一起。如果你现在对它们进行排序，然后你想在字典中搜索它们，你将无法找到它们，因为多个单词的字符是混合的。示例：

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() 的帮助下检查单词列表中的哪些单词可以用给定的变位词构造。然后它 returns 单词列表中所有可能的单词，可以用变位词构造。

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
        )

)

_{（忽略此处的键，因为它们是解决方案的标识符）}

使用递归函数解码字谜不会给出预期的输出

Decoding anagram with recursive function doesn't give expected output

php

function

recursion

anagram

情况

您的代码

解决方案

理论

代码