Anagram Algorithm in PHP

Question

Я полностью новичок с PHP. Сегодня у меня просто проблема, что я не могу понять, как ее решить, даже после поиска google и копания 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... 
?> 

Я надеюсь получить алгоритм как можно более простым, потому что я полностью новичок. И мне жаль, потому что мой английский не так хорош. С уважением, Khiem Nguyen.

Answer 1

(я добавляю это как отдельный ответ, так как это другой способ решения вопроса, чем я упомянул в моем первом вопросе)

Это более сложный способ разработки, который слова в словаре являются частью слова, которое вы ищете; Я оставлю его читателю, чтобы понять, как это работает.

Использование факторизации для определения того, является ли слово анаграммой другого. То, что он будет делать, - это присвоить каждой букве уникальное основное значение; вы можете рассчитать значение букв в данном слове, умножив все значения вместе. 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' 

Answer 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 

Есть несколько дополнительных вещей, которые вы можете сделать - вы можете убедиться, что оба анаграмма и словарное слово имеют одинаковую длину (если это не так, они не могут быть анаграммами); и вам также нужно будет выяснить, как обращаться с буквами, которые встречаются несколько раз в словарном словаре, но только один раз в анаграммном слове (приведенный выше код будет сообщать «aa» как анаграмму «a», например)

Answer 3

У меня возникли проблемы с пониманием вашего вопроса, вашим объяснением вашего кода и самого кода. Вы хотите проверить, является ли произвольное слово анаграммой какого-либо слова в словаре?

Это довольно просто - сделайте массив из 26 целых чисел. Пройдите через входное слово в нижнем регистре, увеличьте массив [letter - 'a'] (или любой другой эквивалент php) на 1 для каждой буквы.

Затем пройдите через словарь и для каждого слова сгенерируйте array_dict таким же образом и проверьте i = 0 ... 25, если array [i] == array_dict [i]. Если они все одинаковые, слова являются анаграммами. Разумеется, установите array_dict на нули после каждого слова.

Другим подходом было бы сортировать буквы в строках и просто сравнивать отсортированные строки. Это хорошо, если вам разрешено модифицировать/препроизводить словарь - вы держите свой словарь предварительно отсортированным, а затем просто сортируете входное слово и сравниваете его со словарными словами. Оптимальное решение, вероятно, будет создавать (в терминах C#, я не знаю PHP извините)

Dictionary<string, List<string>> 

и предобработки словаря по сортировке каждое слово, его поиск в словаре, если список Безразлично» t его создать, и в любом случае добавить слово в список. Затем, когда пользователь вводит слово, вы можете сортировать его и возвращать словарь [sortedword] в качестве результата - все анаграммы, найденные в основном постоянное время (nlogn на длину строки ввода, но константу на размер словаря).

Answer 4

$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); 
} 

Answer 5

Попробуйте функцию строки в случайном порядке?

str_shuffle (string $str) 

Вот некоторые psuedocode:

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?