Thread: anagrams

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    494

    anagrams

    how would i go about coding an algorithm that takes a word and gives its anagram? need some help figuring out the steps i need to take. An anagram is a word created by another word by changing the order of the letters. ex. use -> sue. so this would be equal to 3!, so i would get 6 different words correct?

    what i was thinking of doing is make a copy of the original word - 1st letter and place that letter at the end of the word, but then at some point i will get the same word again . then take the 2nd letter and place it at the end, then take the 3rd letter and place it at the end again.

    or would it be better and more efficient if i ignore the letter all together and focus on arranging the indeces that hold the letters? any suggestions?
    When no one helps you out. Call google();

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You might do a board search for 'permeation'. If you're ever stuck on how to do something in code, try to think of it as how you yourself would do the job. Then break that down into the smallest steps you can think of gradually, and there you'll end up with your pseudocode.

    You can do this task with some loops. Loop through the word starting with the first letter, and switch around the rest of them one at a time. Or you can use recursion, which may be easier.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    494
    you are right this is done using permutation and i know how permutation works but i dont need the actual number of permutation but each word individual, that means i will have to break out of the loop after each permutation, right?
    When no one helps you out. Call google();

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Or just when you hit the end of a string. If you're just moving one character at a time down the line, simply stop when you hit the end.

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Nov 2004
    Location
    USA
    Posts
    516
    nested for loops might be of help to you. keeping first one constant, change the others, here you can use recursions to change the order of the letters. if you use recursions and a loop, i think it will serve your purpose.
    - PING !
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  6. #6
    Registered User
    Join Date
    Mar 2004
    Posts
    494
    wouldnt this create double words?
    When no one helps you out. Call google();

  7. #7
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Quote Originally Posted by InvariantLoop
    how would i go about coding an algorithm that takes a word and gives its anagram? need some help figuring out the steps i need to take.
    The algorithm is available to you if you take a look at the implementation of the STL next_permutation function (in the <algorithm> header). Your task would then be to code a C version of it that works on character arrays... which looks to be fairly simple. Note: this algorithm depends on the initial input string being in sorted order for it to work properly, i.e. you would start by giving it an initial string of "esu" using your example.

    Quote Originally Posted by InvariantLoop
    An anagram is a word created by another word by changing the order of the letters. ex. use -> sue. so this would be equal to 3!, so i would get 6 different words correct?
    You have 6 different permutations yes, but whether or not those permutations equate to actual words is another matter.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    #include <stdio.h>
    int main( void )
    {
            char word[] = "abcdefg";
            int x,z;
            for( x = 1; word[x]; x++ )
            {
                    z = word[x];
                    word[x] = word[x-1];
                    word[x-1] = z;
                    printf("%s\n", word );
            }
            return 0;
    
    }
    Here's one run through. I'll leave the rest to you.

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Mar 2004
    Posts
    494
    yes thats right, the fact that some of the words created have no meaning is not an issue.
    When no one helps you out. Call google();

  10. #10
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    I bet you could come up with a few rules that would help look for words without a dictionary. Perhaps rules like "no more than two vowels in a row", "no more than four consonants in a row", or "no more than two of the same letter in a row i.e. no WWW". Of course, implementing that might be a hassle.

    edit: Of course, if it's not an issue, then I wouldn't bother with it.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  11. #11
    Registered User
    Join Date
    Mar 2004
    Posts
    494
    ah. I need to read hour 12, working with arrays before i actually start doing anything like this. Theres too much i dont understand yet.
    When no one helps you out. Call google();

  12. #12
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    lol,

    Unfortunately, using a permutation algo to solve anagrams is impratical - as you may have realised. A word of nine letters would be 9! and this takes up too much processor time. The solution is simple - implement a letter frequency counter and then check it with a dictionary file.


    Code:
    #include <stdio.h>
    #include<iostream.h>
    #include<string.h>
    #include<fstream.h>
    
    int main()
    {
    
     fstream file_pointer_in;
     fstream file_pointer_out;
     
     file_pointer_in.open("dict.txt",ios::in);
     file_pointer_out.open("contain.txt",ios::out);
    
     int a,b;
     char array[81];
     cout<<"Enter word:"<<endl;
     cin>>array;
     cout<<"Calculating possibilities..."<<endl;
     cout<<" "<<endl;
     cout<<" "<<endl;
     int mass;
     mass = strlen(array);
     
    
     
    
    
     
    
      char alphabet[28]={"/abcdefghijklmnopqrstuvwxyz"};
      int alphacount[26];
      int betacount[26];
     
    
      //initialise
       for (int i=1; i<27; i++)
        {
         alphacount[i]=0;
        }
    
        for(a=0; a<mass; a++)
        {
         
          for(int j=1; j<27; j++)
            {
             if (array[a]==alphabet[j])
              {
              alphacount[j]++;
              }
             }
            }
    
    
     //open dictionary file and read>>
     char x[81];
    
     do{
        file_pointer_in>>x;
        int size;
    
    
        size = strlen(x);
    
        for (int i=1; i<27; i++)
        {
         betacount[i]=0;
        }
    
    
    
    
    
    
        for (int i=0; i<size; i++)
        {
         for (int j=1; j<27; j++)
          {
           if (x[i]==alphabet[j])
            {
             betacount[j]++;
            }
           }
          }
           int counter=0;
           int hello=0;
          for (int k=1; k<27; k++)
          {
           if (betacount[k]==alphacount[k])
            {
            hello++;
            }
    
    
          if (betacount[k]<=alphacount[k])
          {
           counter++;
          }
    
          }
            if (hello==26)
           {
           file_pointer_out<<"** BINGO ***:"<<x<<endl;
           }
           if (counter==26)
           {
           file_pointer_out<<x<<endl;
           }
    
    
          
    Simple yet elegant
              
    
    
    
         
    
    
        }while(file_pointer_in.peek()!=EOF);
        cout<<"END-";
        int stop;
        cin>>stop;
    
        file_pointer_in.close();
        file_pointer_out.close();
    
    
    }

  13. #13
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    This is the C board...C++ and C make look a lot alike, but they're not the same thing.
    If you understand what you're doing, you're not learning anything.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. anagram program help
    By pjr5043 in forum C++ Programming
    Replies: 50
    Last Post: 04-28-2008, 07:32 PM
  2. It's your turn (job anagrams)
    By Salem in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 05-18-2007, 12:18 PM
  3. anagrams problems with n factorial
    By treenef in forum C++ Programming
    Replies: 9
    Last Post: 03-29-2005, 01:52 AM
  4. Anagrams
    By misswaleleia in forum C Programming
    Replies: 2
    Last Post: 05-31-2003, 06:37 PM
  5. Anagrams
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 03-08-2002, 04:40 PM