拼字游戏字生成器

看着我的兄弟在像拼字游戏一样的iphone游戏中作弊后，我想知道什么是algotithm behing它。拼字游戏字生成器

鉴于一些字母：A B C T EË

和SQL满桌的正确的单词。

我将如何创建所有字母组合，用于选择后续事件：从单词IN（'A'，'AT'，...）中选择*从这些组合中选择*是否正确？

另一种可能的方式可能是一个SQL表，每个单词列中的每个字母都包含一个字母。但后来系统应该验证任何单词形式选择有更多的时间相同的字母给出。

例：

C1，C2，C3 C4 三通空气

这个问题仅仅是喂养的好奇心，学习巫婆算法它可能是用于创建所有这些组合（完整和部分给予字母）以后检查它们是否存在。

谢谢！

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

来源

2012-04-21 user1343998

的可能重复（http://stackoverflow.com/questions/ 880559 /算法对获得-A-列表中，所有的词 - 这 - 是 - 字谜 - 的 - 所有子-scrabb）。另请参阅http://stackoverflow.com/questions/tagged/scrabble – JJJ 2012-04-21 13:21:47

那么最简单的算法（但也是最没有效率的）就是简单地检查所有可能的组合并查询数据库。我也很想知道这里会发生什么。 – 2012-04-21 13:22:10

这里是伟大的文章，大约World fastest scrabble program

你只应该在Descrete数学（字自动定）有一定的了解。希望它会帮助你:)

来源

2012-04-21 13:22:30

我会尝试像

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

等。但我确定必须有更专业的解决方案！

来源

2012-04-21 13:23:35

当您多次使用相同的字母时，这不起作用。 – 2012-04-21 13:26:32

好吧，它确实需要更聪明的算法，但是对于你有双倍的字母，你可以写'（（像'％E％'这样的字或'％E％E％'这样的字）而不是'％' Ë％E％E％'）'。如果我坐下来认真思考这件事，我相信我可以做到这一点！ – 2012-04-21 13:29:44

我也想过，但所有这些，你只会得到最大的单词，而不是那些只使用5个字母中的3个给出的单词。也许使用这个，每个字母组合应该有一个选择并使用“长度”。但是使用一切不能快速的东西。 – user1343998 2012-04-22 09:58:14

要查找所有可能的有效字这是下面的步骤

找到所有可能的组合
查找每个排列的组合中的每个字
搜索数据库的话
列表中字

脚本

个

$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-21 14:13:12 Baba

我终于得到它的工作。

如果有人在做自我字产生过兴趣，这是我做到了。

的MySQL，具有一个表：

[id] , [Word]

每个长度的图：

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

PHP端：

使用巴巴的功能，我提出的阵列，其中：阵列[2]是长度为2的字母组合，依此类推。

最后，所有我必须做的是选择每个阵列的观点类似

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

必须有一个更快的方法，但比第二（本地主机）和字diccionary的700K取得了少它的方式。

来源

2012-05-01 17:17:10 user1343998

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

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-11 04:19:50

拼字游戏字生成器

回答

相关问题