#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2004
    Posts
    33
    Rep Power
    0

    Anagram Algorithm


    I am trying to create an anagram algorithm. It must be a recursive backtracking algorithm. For example if the input is "raziber" the ouput would be "bizarre" and "brazier". If anyone can offer me some help in creating this algorithm it would be greatly appreciated.
  2. #2
  3. Doggie
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2003
    Location
    Seattle, WA
    Posts
    751
    Rep Power
    13
    First thing you need is a dictionary files of legal words to use.

    Then just loop through all the combinations the letters can make up. Check that against the dictionary. You could have it cancel the loop once a word is started that no word in the dictionary starts with. (ie: start with 'rz', no words found, skip rest of combinations starting with 'rz')

    Make sense?

    You'll have to google to see if you can find a free dictionary file. Good luck.
    "Science is constructed of facts as a house is of stones. But a collection of facts is no more a science than a heap of stones is a house." - Henri Poincare
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2004
    Posts
    33
    Rep Power
    0
    yea i already have the dictionary part all setup using a dlb trie, as of right now a user can enter a phrase and my program will say if it is a Valid word, a Valid prefix, or Invalid. I just don't know the best way to go about writing an algorithm to go through each combination of the phrase using recursive backtracking.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    Code:
    <?
    
    class backtrack {
    
      # constructor
      function backtrack($input_array)
      {
        // the array you want to backtrack and get each configuration of
        $this->_array = $input_array;
    
        // the current configuration of elements
        $this->configuration = array();
    
        // if $this->taken[$pos] == false, $this->_array[$pos] is yet to be used
        // in the current configuration
        $this->taken = array();
    
        // set all as NOT taken
        for ($i=0; $i<count($this->_array); $i++) $this->taken[$i] = false;
      }
    
    
      # recursive function:
      # fill each position ($pos) in configuration by trying each element from $this->_array
      function do_backtrack($pos)
      {
        // if configuration is complete
        if ($pos == count($this->_array))
        {
          $this->test_configuration();
          return;
        }
    
        // try fill each position in the configuration with each element in $_array.
        // but we can only use it if it's not in the current configuration (ie its 'taken')
        for ($i=0; $i<count($this->_array); $i++)
        {
          if ($this->taken[$i]) continue;
    
          $this->configuration[$pos] = $this->_array[$i]; // take it
          $this->taken[$i] = true;      // set it as now taken
          $this->do_backtrack($pos+1);  // continue backtracking to get rest of configuration
          $this->taken[$i] = false;     // set as untaken as we try next configuration
        }
      }
    
    
      # we can do something with configuration here since configuration is done
      # but we currently just print it out
      function test_configuration()
      {
        for ($i=0; $i<count($this->_array); $i++) 
            print $this->configuration[$i].' ';
        print '<br>';
      }
    
    }
    
    $btrack = new backtrack(array('1','3','5'));
    $btrack->do_backtrack(0);
    Last edited by lazy_yogi; January 22nd, 2004 at 06:39 PM.
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2004
    Posts
    33
    Rep Power
    0
    is there a wayto do it without using pointers?? I am using C++ also.
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    This doesnt use pionters.

    And it should be a straight conversion over to c++.

    Just declare 3 vector objects in the class which I created in the constructor. And declare the variables such as $i. Otherwise its a straight conversion to c++
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2004
    Posts
    33
    Rep Power
    0
    I'm sorry i am kinda confused with the sintax, "this->array" that is a vector? I am really not good with vectors, I have only used them once before, how do they differ from arrays? I really appreciate all your help here.
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Posts
    325
    Rep Power
    12
    $this->_array
    Anything infront of '$this' is a class varible
    just as in c++

    I've declared '_array' as the name for the class variable that holds the initial array

    Learn to use vectors. They do all the work for you in c++. They hold the length of the vector so you don't have to iterate throug it each time. It also adds elements for you so you never have to resize the vector yourself manually. Has some other nice features like searching and so on.

    Seach the web for how to use a vector in c++ and ask for help in the c/c++ forum if you still don't understand it.
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2004
    Posts
    33
    Rep Power
    0
    I am trying to create an Anagram finder. ok this is what I came up with so far, keep in mind i have a working dictionary dlb trie that tells me if a phrase is a Valid Prefix, Valid Word, or Invalid. So basically I just have to come up with this recursive bactracking algorithm to find the anagrams. usedChars is 0 if char was not used and 1 if char was used, origWord is phrase taken from user, currWord is phrase being built to form anagram. I am getting some funny output. Any suggestions would be appreciated.

    code:

    void findAnagram(int usedChars[], char* origWord[], char* currWord[]){

    if(Valid Prefix){

    for(i=0; i<strlen(origWord); i++){

    //test to see if char was used already
    if(usedChars[i] == 0){
    currWord[i] = origWord[i]; //append char to end of curr
    usedChars[i] = 1; //set char to 1 saying it was used

    //recurse
    find(usedChars, origWord, currWord);

    //remove last char from curr
    i--;
    currWord[i] = '\0';

    //set char to 0 saying it was unused
    usedChars[i] = 0;
    }//end if
    }//end for

    }//end if

    else if(currWord == Valid word){
    cout<<anagram = <<currWord<<endl;
    }//else if
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2009
    Posts
    3
    Rep Power
    0
    Originally Posted by catz423
    I am trying to create an anagram algorithm. It must be a recursive backtracking algorithm. For example if the input is "raziber" the ouput would be "bizarre" and "brazier". If anyone can offer me some help in creating this algorithm it would be greatly appreciated.


    Hey I'm doing a very similar project and was wondering where you found your dictionary, and if it's comprehensive (the best i've been able to find so far are word lists of about 2/3k words which omit some pretty important ones!)

    muchos gracias hombre
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    Reviving a five year old thread was pointless.
    I no longer wish to be associated with this site.
  22. #12
  23. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2009
    Posts
    1
    Rep Power
    0
    Originally Posted by jimbobstrangemo
    Hey I'm doing a very similar project and was wondering where you found your dictionary, and if it's comprehensive (the best i've been able to find so far are word lists of about 2/3k words which omit some pretty important ones!)

    muchos gracias hombre
    Sorry, I can't post URLs.

    Try google search for "owl-lwl.txt". It's an official Scrabble tournament word list.

    I used the OWL word list as one of the sources for my Xworder.com project.

    You can also find various versions of the linux.words file which is used for spellcheck in Linux.

    Good luck,

    - bbzippo.

IMN logo majestic logo threadwatch logo seochat tools logo