Генератор слов Scrabble

Question

После просмотра моего брата, обманывающего игру в iphone, подобную scrabble, мне было интересно, что это за альготизм.

Учитывая некоторые буквы: A B C T E E

И SQL переполнена таблица правильных слов.

Как создать все комбинации букв для создания afterwars a select like: Выберите * из слов, где слово IN ('A', 'AT', ...), просто чтобы взять из этих комбинаций те, которые правильны? ¿

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

Ex:

c1 c2 c3 c4 тройника воздуха

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

Спасибо!

шрифта: http://icon.cat/worder/wordsfinder

Answer 1

Вот большая статья о World fastest scrabble program

Вы просто должны иметь некоторые знания в Дискретный Math (Слово automāts). Надеюсь, что это поможет :)

Answer 2

Я хотел бы попробовать что-то вроде

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

и так далее. Но я уверен, что должно быть больше профессиональных решений!

Answer 3

Чтобы найти все возможные действительные слова этого являются следующими шагами

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

Answer 4

я, наконец, получил это работает.

Если кто-то заинтересован в создании генератора собственных слов, вот как я это сделал.

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 из 70оК сделали его путь.

Answer 5

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

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