4

スクラブルのようなiPhoneゲームで兄が不正行為をしているのを見た後、私はそれの背後にあるアルゴリズムが何であるか疑問に思っていました.

いくつかの文字を考える: ABCTEE

そして、正しい単語でいっぱいの SQL テーブル。

afterwars を次のように選択するための文字のすべての組み合わせを作成するにはどうすればよいですか?

別の考えられる方法は、各単語の列にすべての文字を含む SQL テーブルです。しかしその後、システムは、選択された単語から同じ文字がより多く含まれていることを確認する必要があります。

元：

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 の関数を使用して、配列を作成しました。配列 [2] は長さ 2 の文字の組み合わせなどです。

最後に、私がしなければならなかったのは、次のようなビューへの各配列の選択です

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

もっと速い方法があるに違いありませんが、1 秒未満 (localhost) で、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

世界最速のスクラブルプログラムに関する素晴らしい記事はこちら

Descrete Math(Word Automats) に関する知識が必要です。それがあなたを助けることを願っています:)

于 2012-04-21T13:22:30.723 に答える