3

I'm totally a newbie with PHP. Today I just got a problem that I can't know how to solve, even after searching google and digging SOF. It's the Anagram algorithm.

So basically, I understand the problem here : When user input a string, I split it and compare with my library (a given array), then I will have to join it by 2-3-...etc characters to compare again, it's exactly where I'm stuck now, I don't know how to join the elements of the array.

Here is the code that I'm implementing, and also a sample dictionary.

I have a self-made dictionary with these elements in the array $dict. And i have a form for users to input a string, the string inputted will be passed to the code below and declared as $anagram. I have to split the string inputted to compare with my dictionary. But I don't know how to join them like comparing 2 letters, 3 letters...etc...and so on, to the dictionary.

<?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...
?>

I hope to get the algorith as simple as possible because I'm totally a newbie. And I'm sorry because my english is not so good. Best regards, Khiem Nguyen.

4
  • found two links: sourceforge.net/projects/phpag and phpclasses.org/browse/file/12539.html
    – user745235
    Commented May 17, 2012 at 14:57
  • Thanks Gerep, I've read through them but it's like useless because it's too complicated that I cannot understand. I expect to have a simpler algorithm, by just joining elements of the string by using the loops and compare it with the library.
    – khiemnn
    Commented May 17, 2012 at 15:03
  • 1
    would it not be better to sort the anagram characters alphabetically and in the loop do the same for each dictionary word. if the anagram is a substring of the dictionary word then its an anagram
    – gunnx
    Commented May 17, 2012 at 15:07
  • Here's a one-line answer to this question stackoverflow.com/a/32156857/4233593 Commented Oct 26, 2016 at 14:15

6 Answers 6

19

(I'm adding this as a separate answer, as it's a different way of dealing with the issue than I mentioned in my first issue)

This is a more complex way of working out which words in the dictionary are part of the word that you're looking for; I'll leave it up to the reader to work out how it works.

It's using factorisation to work out whether a word is an anagram of another. What it will do is assign each letter a unique, prime value; you can calculate the value of the letters in a given word by multiplying all the values together. CAT, for example, is 37 * 5 * 3, or 510. If your target word factors to the same number, you can be sure that the one is an anagram of the other.

I've ordered the prime numbers by how common they are in UK English, to keep the factors generated smaller.

<?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/>");
    }
}

For what it's worth, I think this is a much more elegant solution - you can speed it up by pre-calculating the values in your dictionary. If you go through and work out the factors for every word in your dictionary, you can do the searching direct in the database:

SELECT word FROM dictionary WHERE wordFactor='$factorOfThisWord'
9
  • Can I respectfully ask you to add comment for the code above? I don't know what the function factorise does.
    – khiemnn
    Commented May 18, 2012 at 14:26
  • 1
    Actually, I deliberately left the comments out; it's not that complicated a piece of code, so you should be able to figure out what it's doing. Try adding lots of var_dump calls to see what variables are being set, and take it from there.
    – andrewsi
    Commented May 18, 2012 at 14:38
  • Some of us are not looking to implement this, but would still like to understand how this works. Please post comments for our sake... Commented Jun 26, 2012 at 22:06
  • @andrewsi I am trying for long word -- Where the script is failing. eg. for $searchWord = "hastededrs"; Result are not displaying. :(
    – mujaffars
    Commented Sep 22, 2015 at 13:17
  • @mujaffars - it shouldn't have any problems with something that short. All I can suggest is that you add plenty of debugging to your code, and try to figure out why it's failing. Try adding an else to the if - does that show anything, or are you getting a completely blank screen?
    – andrewsi
    Commented Sep 22, 2015 at 13:46
2

I can't quite follow what your code is doing; but if you want a simple anagram checker, the pseudocode would be something like:

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

There are a couple of extra things you can do - you can make sure that both the anagram and the dictionary word are the same length (if they're not, they can't be anagrams); and you'll also need to figure out how to deal with letters that occur multiple times in the dictionary word but only once in the anagram word (the above code would report 'aa' as an anagram of 'a', for example)

11
  • I'm sorry i think i put you guys in the middle of the trouble. From the start, there is a form for the users to input an arbitrary word, that explains why there is a $_POST there. @andrewsi I think your pseudo code has something wrong isn't it? Because you have to split the string user inputted, then join them back to compare, because maybe in the $dict just got something 1 letter only, like "a", "e",etc...
    – khiemnn
    Commented May 17, 2012 at 15:40
  • Why do you need to join the string back together to compare them? The logic above will split both the search word and the dictionary words into arrays, and compare the contents of each array; it doesn't matter if the dictionary words is one letter - you'll end up with an array that just has one item in it.
    – andrewsi
    Commented May 17, 2012 at 15:44
  • I have to split because of this : for example, my dictionary above contains 'hat' and 'e', and the string user inputs is 'hatedes'. The main goal is to print out the anagram matched with the dict, so this time it will print out 'hat' 'e' and 'des' because the dict contains it. If you compare the contents of each array, how if the array the user inputs is longer than the array of the dictionary?
    – khiemnn
    Commented May 17, 2012 at 16:44
  • It doesn't matter how long the arrays are; you just need to check to make sure that the contents of the one match the contents of the other. So if the dictionary word is 'a', and the word entered is 'aardvark', you'd match because the a is there. It doesn't matter what the other letters in the word are.
    – andrewsi
    Commented May 17, 2012 at 16:56
  • I didn't say anything about sorting - did you mean that for someone else?
    – andrewsi
    Commented May 17, 2012 at 16:59
0

I am having trouble understanding your question, your explanation of your code and the code itself. Do you want to check whether an arbitrary word is an anagram of some word in the dictionary?

That's pretty simple - make an array of 26 integers. Go through the input word in lowercase, increase array[letter - 'a'] (or whatever the php equivalent is) by 1 for each letter.

Then go through the dictionary and for each word generate array_dict in the same way, and check for i = 0...25 if array[i] == array_dict[i]. If they are all the same, the words are anagrams. Set array_dict back to zeros after each word, of course.

Another approach would be to sort the letters in the strings, and simply compare the sorted strings. This one is good if you are allowed to modify/preprocess the dictionary - you keep your dictionary pre-sorted, and then just sort the input word and compare it to the dictionary words. The optimal solution would probably be to create an (in C# terms, I don't know php sorry)

Dictionary<string, List<string>>

and preprocess your dictionary by sorting each word, looking it up in the dictionary, if the list doesn't exist create it, and in either case add the word to the list. Then when the user inputs the word, you can sort it and return dictionary[sortedword] as the result - all anagrams found in basically constant time (nlogn on input string length, but constant on dictionary size).

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);
}
4
  • Thanks gunnx, but i have this to wonder about. For example my dictionary have the word 'hat', then you sort it, it become 'aht', the string the user inputs is 'ath'. So if you sort both of them, they match! But have a look, the word the user inputted does not match the dict (ath and hat).
    – khiemnn
    Commented May 17, 2012 at 16:47
  • You sort the input word too, as shown in the code $anagramSorted
    – gunnx
    Commented May 17, 2012 at 18:28
  • If you sort both the inputted string and the word in the dict, It's totally changed! Like my example above I can give you more : the dict has 'good', the user inputs 'doog', If you sort both, they totally match. But the inputted string does not match and it's not in the dict.
    – khiemnn
    Commented May 18, 2012 at 2:46
  • 1
    sorry not sure what you mean but I see you've accepted an answer so hope it works for you.
    – gunnx
    Commented May 18, 2012 at 21:30
0

Try the string shuffle function?

str_shuffle ( string $str )

Here is some 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?
0

This function will take the string and return the count anagrams present in the string.

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');

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.