要查找所有可能的有效字這是下面的步驟
- 找到所有可能的組合
- 查找每個排列的組合中的每個字
- 搜索數據庫的話
- 列表中字
腳本
個
$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
的可能重複(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