4

在看到我的兄弟在像拼字游戏这样的 iphone 游戏中作弊后，我想知道它的算法是什么。

给定一些字母：ABCTEE

并且 SQL 表中充满了正确的单词。

我将如何创建所有字母组合以便在之后进行选择，例如：从单词 IN（'A'、'AT'、...）的单词中选择 *，只是从这些组合中获取正确的组合？¿

另一种可能的方式可能是一个 SQL 表，其中每个单词的每个字母在一列中。但之后系统应验证 select 的任何单词是否有更多的时间与给定的相同字母。

前任：

c1 c2 c3 c4 三通空气

这个问题只是为了满足好奇心，并学习巫婆算法，它可能用于创建所有这些组合（带有完整和部分给定字母），以便事后检查它们是否存在。

谢谢！

字体：http: //icon.cat/worder/wordsfinder

4

5 回答 5

2

要找到所有可能的有效单词，请执行以下步骤

  1. 找到所有可能的组合
  2. 找到组合中每个单词的每个排列
  3. 在数据库中搜索单词
  4. 列出单词

脚本

$tiles  = array( "A", "B", "C", "T", "E", "E") ;
$words = array();
$set = powerSet($tiles,2);

$mysql = new mysqli("localhost","root","","word");
$sql = "SELECT id from dic WHERE word = '%s'" ;

foreach ($set as $key => $value)
{
    $word = implode("", $value);
    $wordPermutation = permute($word);

    foreach($wordPermutation as $keyWord)
    {
        if(!in_array($keyWord, $words))
        {
            //if($result = $mysql->query(sprintf($sql,$keyWord)))
            //{
                //var_dump(sprintf($sql,$keyWord));
                //if($result->num_rows > 0)
                //{
                    $words[] = $keyWord ;
                //}
            //}
        }
    }
}


print_r($words);

功能

function powerSet($in, $minLength = 1, $max = 10) {
    $count = count ( $in );
    $members = pow ( 2, $count );
    $return = array ();
    for($i = 0; $i < $members; $i ++) {
        $b = sprintf ( "%0" . $count . "b", $i );
        $out = array ();
        for($j = 0; $j < $count; $j ++) {
            if ($b {$j} == '1')
                $out [] = $in [$j];
        }
        if (count ( $out ) >= $minLength && count ( $out ) <= $max) {
            $return [] = $out;
        }

    }
    return $return;
}


function permute($str) {
    if (strlen($str) < 2) {
        return array($str);
    }
    $permutations = array();
    $tail = substr($str, 1);
    foreach (permute($tail) as $permutation) {
        $length = strlen($permutation);
        for ($i = 0; $i <= $length; $i++) {
            $permutations[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i);
        }
    }
    return $permutations;
}

请注意，我commented退出了数据库验证部分，以便演示可以工作

看演示

http://codepad.viper-7.com/oG6E6w

于 2012-04-21T14:13:12.003 回答
1

我会尝试类似的东西

WHERE (word like '%A%' and not word like '%A%A%')
  AND (word like '%B%' and not word like '%B%B%')

等等。但我相信一定有更专业的解决方案！

于 2012-04-21T13:23:35.250 回答
1

我终于让它工作了。

如果有人对制作自我单词生成器感兴趣，我就是这样做的。

MySQL，一个表：

[id] , [Word]

每个长度的视图：

V1 = Select Word from TABLE where LENGTH(Word) = 1
V2 = Select Word from TABLE where LENGTH(Word) = 2
[...]

php端：

使用 baba 的函数，我创建了一个数组，其中：array[2] 是长度为 2 的字母组合，依此类推。

最后，我所要做的就是为每个数组选择一个视图，例如

Select Word from V3 where Word like ('asd','dsa',....);

必须有一种更快的方法，但不到一秒（本地主机）和 700K 的单词字典就成功了。

于 2012-05-01T17:17:10.077 回答
1

实现解扰的更好方法是使用字谜。因此，不要使用包含所有可能单词的库，而是使用关联数组，使用构成单词的字母作为索引。

anagram['aer'] = ['are', 'ear', 'era']

要实现这一点，请遍历所有字典单词并将每个单词推入一个数组，其中索引是按字母顺序排列的单词的字母。

for(var i = 0; i < dictionary.length; i++) {
//Loop through dictionary array
    var str = words[i].split('').sort().join('');
    //break apart the word and sort it alphabetically
    if(!anagram[str]) {
        //check if there is already an index with that same anagram
        anagram[str] = [];
    }

    anagram[str].push(words[i]);
    //Add the word to the anagram array

}

这种方式使您可以快速索引库，而无需经历数千种可能的排列。

javascript中此方法的一个示例：Word Unscrambler

于 2013-10-11T04:19:50.827 回答
0

这是关于世界上最快的拼字游戏程序的精彩文章

您应该对离散数学（Word Automats）有一些了解。希望它会帮助你:)

于 2012-04-21T13:22:30.723 回答