3

私は完全にPHPの初心者です。今日、グーグルを検索してSOFを掘った後でも、解決方法がわからないという問題が発生しました。これはアナグラムアルゴリズムです。

つまり、基本的に、ここでの問題を理解しています。ユーザーが文字列を入力すると、それを分割してライブラリ（特定の配列）と比較します。次に、2〜3文字で結合する必要があります。それはまさに私が今立ち往生しているところです、私は配列の要素を結合する方法がわかりません。

これが私が実装しているコードとサンプル辞書です。

配列$dictにこれらの要素を含む自作の辞書があります。そして、ユーザーが文字列を入力するためのフォームがあります。入力された文字列は、以下のコードに渡され、$anagramとして宣言されます。入力した文字列を分割して辞書と比較する必要があります。しかし、2文字、3文字などを辞書と比較するなど、それらを結合する方法がわかりません。

<?php

$dict = array(
'abde',
'des',
'klajsd',
'ksj',
'hat',
'good',
'book',
'puzzle',
'local',
'php',
'e');

$anagram = $_POST['anagram'];
//change to lowercase
$anagram = strtolower($anagram);

//split the string
$test = str_split($anagram);

//compare with $dict for the first split without joining
for ($i=0; $i<strlen($anagram); $i++) {
    if ($test[$i]==$dict[$i]) {
        echo $test[$i]."<br />";
    }
}

//problem: how to join elements of the array in the loops
//like user inputs "hellodes"
//after echo "e", how to join the elements like: h-e,h-l,h-l,h-o,h-d,h-e,h-s
//and then h-e-l,h-e-l,h-e-o...etc...
?>

私は完全に初心者なので、アルゴリズムをできるだけ単純にしたいと思っています。そして、私の英語があまり上手ではないので、ごめんなさい。よろしく、キエムグエン。

4

6 に答える 6

19

（これは、最初の号で述べたのとは異なる問題への対処方法であるため、別の回答として追加します）

これは、辞書内のどの単語が探している単語の一部であるかを判断するためのより複雑な方法です。それがどのように機能するかを理解するのは読者に任せます。

因数分解を使用して、単語が別の単語のアナグラムであるかどうかを判断します。それが行うことは、各文字に一意のプライム値を割り当てることです。すべての値を掛け合わせることで、特定の単語の文字の値を計算できます。たとえば、CATは37 * 5 * 3、つまり510です。ターゲットの単語が同じ数に因数分解される場合、一方が他方のアナグラムであると確信できます。

生成される因子を小さく保つために、英国英語での素数の一般性順に並べました。

<?php

function factorise($word)
{
    // Take a number, split it into individual letters, and multiply those values together
    // So long as both words use the same value, you can amend the ordering of the factors 
    // as you like

    $factors = array("e" => 2, "t" => 3, "a" => 5, "o" => 7, "i" => 11,
        "n" => 13, "s" => 17, "h" => 19, "r" => 23, "d" => 29,
        "l" => 31, "c" => 37, "u" => 41, "m" => 43, "w" => 47,
        "f" => 53, "g" => 59, "y" => 61, "p" => 67, "b" => 71,
        "v" => 73, "k" => 79, "j" => 83, "x" => 89, "q" => 97,
        "z" => 101);

    $total = 1;

    $letters = str_split($word);

    foreach ($letters as $thisLetter) {
        if (isset($factors[$thisLetter])) {
            // This will skip any non-alphanumeric characters.
            $total *= $factors[$thisLetter];
        }
    }

    return $total;
}

$searchWord = "hasted";

$dict = array("abde", "des", "klajsd", "ksj", "hat", "hats");

$searchWordFactor = factorise($searchWord);

foreach ($dict as $thisWord) {
    // Factorise each word that we're looking for
    // If the word we've just factored is an exact divisor of the target word, then all the 
    // letters in that word are also present in the target word
    // If you want to do an exact anagram, then check that the two totals are equal

    $dictWordFactor = factorise($thisWord);

    if (($searchWordFactor % $dictWordFactor) == 0) {
        print ($thisWord . " is an anagram of " . $searchWord . "<br/>");
    }
}

価値のあることとして、これははるかに洗練されたソリューションだと思います。辞書の値を事前に計算することで、スピードを上げることができます。辞書内のすべての単語の要素を調べて計算すると、データベースで直接検索を実行できます。

SELECT word FROM dictionary WHERE wordFactor='$factorOfThisWord'
于 2012-05-18T14:03:32.343 に答える
2

私はあなたのコードが何をしているのか完全には理解できません。ただし、単純なアナグラムチェッカーが必要な場合、擬似コードは次のようになります。

get array of letters in my anagram
for each word in the dictionary
    get array of letters in this word
    for each letter in my anagram
        is this letter also in the word?
            if no, move on to the next word
    if we get here, it's an anagram

実行できる追加のことがいくつかあります。アナグラムと辞書の単語の両方が同じ長さであることを確認できます（そうでない場合は、アナグラムにすることはできません）。また、辞書の単語に複数回出現するが、アナグラムの単語に1回だけ出現する文字を処理する方法を理解する必要があります（たとえば、上記のコードは「aa」を「a」のアナグラムとして報告します）

于 2012-05-17T15:10:08.173 に答える
0 
$dictionary = array("kayak");

$anagram = "kayak";

$anagramSorted = sortString($anagram);


foreach ($dictionary as $word)
{
    $wordSorted = sortString($word);
    if ($wordSorted == $anagramSorted)
    {
       echo 'true';
    }
}

function sortString($s)
{
    $chars = array();
    $length = strlen($s);
    for ($i=0;$i<$length;$i++)
    {
       $chars[] = $s[$i];
    }
    sort($chars);

    return implode("",$chars);
}
于 2012-05-17T15:58:04.147 に答える
0

あなたの質問、あなたのコードの説明、そしてコード自体を理解するのに苦労しています。任意の単語が辞書内のある単語のアナグラムであるかどうかを確認しますか？

これは非常に簡単です。26個の整数の配列を作成します。入力単語を小文字で調べ、array [letter-'a']（またはphpに相当するもの）を文字ごとに1ずつ増やします。

次に、辞書を調べて、単語ごとに同じ方法でarray_dictを生成し、array [i] ==array_dict[i]の場合はi=0...25を確認します。それらがすべて同じである場合、単語はアナグラムです。もちろん、各単語の後にarray_dictをゼロに戻します。

別のアプローチは、文字列内の文字を並べ替え、並べ替えられた文字列を単純に比較することです。これは、辞書の変更/前処理が許可されている場合に適しています。辞書は事前に並べ替えられたままで、入力された単語を並べ替えて辞書の単語と比較するだけです。最適な解決策は、おそらく（C＃の用語では、phpは申し訳ありませんがわかりません）を作成することです。 

Dictionary<string, List<string>>

各単語を並べ替えて前処理し、辞書で検索します。リストが存在しない場合は作成し、いずれの場合もその単語をリストに追加します。次に、ユーザーが単語を入力すると、その単語を並べ替えて、結果としてdictionary [sortedword]を返すことができます。すべてのアナグラムは基本的に一定の時間で見つかります（入力文字列の長さはnlognですが、辞書のサイズは一定です）。

于 2012-05-17T15:27:44.043 に答える
0

文字列シャッフル機能を試してみませんか？

str_shuffle ( string $str )

ここにいくつかの擬似コードがあります：

Get random string from array
store string copy (Not shuffled)
string shuffle another copy
echo shuffled string
get users guess
parse guess (Remove illegal characters)
if parsed guess = string
    reward
else
    ?let user try again?
于 2013-11-19T15:52:58.277 に答える
0

この関数は文字列を受け取り、文字列に存在するカウントアナグラムを返します。

function countingAnagrams($str)
    {
        $str_arry = [];
        $anagrams = 0;
        $str_arry= explode(' ', $str);
        for ($i = 0; $i < count($str_arry); $i++) {
            $str_cmp = $str_arry[$i];
            for($k = 0; $k < count($str_arry); $k++){
                if($i != $k){
                    $str_rev = $str_arry[$k];
                    if (count_chars($str_cmp, 1) == count_chars($str_rev, 1))
                    {
                        unset($str_arry[$i]);
                        $str_arry = array_values($str_arry);
                        $anagrams++;
                    }
                }
            }
        }
        return $anagrams;
    }


echo  countingAnagrams('cars are residing on my arcs');
于 2020-03-07T10:42:43.900 に答える