Thread: anagrams problems with n factorial

  1. #1
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374

    anagrams problems with n factorial

    Say I wanted to build an anagram solver. What would be the best way to do this.

    Should I try to use the 'factorial' information to generate all the combinations of letters and then check them for legality using a dictionary file.

    Code:
    For example, what word is this: h,e,t
    
    teh
    the <<solution
    het
    hte
    eth
    eht  
    
     Answer *the*
    There are three letters so there will be 3! possible solutions.
    (N.b. 3! is read as 3x2x1=6). To calculate the factorial of a number is easy however, creating a permutation generator is more difficult.

    Moreover, I would imagine a permutation generator to have a *recursive* solution. (For those who are unfamiliar with the term, it means calling a function from within a function.) Anyone who has tried to create a recursive function will know it's a complete mind f***. lol

    Secondly, attempting to solve a word of more than nine letters would take a reasonably long time. Wouldn't it?

    How do I this and is this the most efficient way to go about.


    Ps. I'm still trying to crack this alegra solver without using binary trees to evaluate nested brackets. It's proving quite difficult. argh

  2. #2
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    The STL provides a way to construct permutations: in <algorithm> we have next_permutation() and friends.

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    >>Ps. I'm still trying to crack this alegra solver without using binary trees to evaluate nested brackets. It's proving quite difficult. argh


    I'm working on this approach as well but was on vacation last week and didn't have time to work on it then. Will try some more now that I'm back.
    You're only born perfect.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    847
    I don't think you'll need to compare every permutation to every word in the dictionary. That would take a long time.
    When you generate a new permutation you could check it against language rules for example I don't think there are any words with 3 'a's in a row, but then again if you allow anograms of acanyms (sp?) then that idea wont work.

  5. #5
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    An idea I had was to break the dictionary into sections (in example, splitting it by letter). You could also sort the dictionary by frequency of occurence.

  6. #6
    Registered User samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Newport
    Posts
    382
    Quote Originally Posted by elad
    >>Ps. I'm still trying to crack this alegra solver without using binary trees to evaluate nested brackets. It's proving quite difficult. argh
    It should be quite simple if you use a stack.

  7. #7
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    Erm yeah,

    After a bit of research I realised using a permutation generator to solve anagrams is a waste of time! Much better is to use a letter frequency counter and then to compare this with the letter frequency count of words within a dictionary file.

    To illustrate, say I have the word : a,t,r,s
    in its jumbled form. Now I count the number of times each alphabet occurs. So:

    Code:
    a=1, t=1,  r=1,  s=1:
    Now I do the same for every word in the dictionary file and output matches to the screen.

    In this case the dictionary would find two matches, *star* and rats*
    since both words have the same *LETTER FREQUENCY COUNT*. As it turns out, this method to solve anagrams is incredibly quick!

    Moreoever, on a completely different note, I have hypothesised that the same method can be used to identify terms of an algebraic expression. For example I could use it to identify which terms I need collect and then add the coefficients.

    Code:
    =5xcv+8xvc+7nm 
    = 13xcv+7nm

    So getting back to this anagram solver. OK. First you will need a dictionary file. Go to the following web address, select all and save it in a notepad file. Name that file 'dictionary.txt'. Make sure this file is in your Dev++ folder.

    http://www.newlife4square.org/progs/words.lex


    Great. Now copy and paste this code into your program and you're done.


    Code:
    #include <iostream>
    #include<string.h>
    #include<fstream>
    using namespace std;
    int main()
    {fstream file_pointer_in;fstream file_pointer_out;
     file_pointer_in.open("dictionary.txt",ios::in);
     file_pointer_out.open("treenef.txt",ios::out);
     int a,b;char array[81];cout<<"Plz nta ur word:"<<endl;
     cin>>array;cout<<"Hacking..Your system...cough.cough"<<endl;
     cout<<" "<<endl;cout<<" "<<endl;int mass;mass = strlen(array);
     char alphabet[28]={"/abcdefghijklmnopqrstuvwxyz"};
     int alphacount[26];int betacount[26];
     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]++; }}}
    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 treenef=0;for (int k=1; k<27; k++)
    {if (betacount[k]==alphacount[k]){treenef++;}
    if (betacount[k]<=alphacount[k]){ counter++;}}if (treenef==26)
    {file_pointer_out<<"** BINGO ***:"<<x<<endl;cout<<x<<endl;}
    if (counter==26){file_pointer_out<<x<<endl;}}
    while(file_pointer_in.peek()!=EOF);cout<<"Quilt (y/n)";
    int stop;cin>>stop;
    file_pointer_in.close();file_pointer_out.close();}
    Lol I love that syntax don't you?

  8. #8
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    I was just about to say, using permutation would be encredibly slow with longer words... especially in recursive form... consider:

    photofinishing: 87,178,291,200 possibilities
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  9. #9
    Registered User Scribbler's Avatar
    Join Date
    Sep 2004
    Location
    Aurora CO
    Posts
    266
    You could probably speed it up a bit more by first discarding all words that don't match total character count. As in your above example, you then wouldn't waste time comparing the letter frequency to words with a total character count != 4.
    Last edited by Scribbler; 03-29-2005 at 02:03 AM.

  10. #10
    Registered User samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Newport
    Posts
    382
    Quote Originally Posted by treenef
    Erm yeah,

    After a bit of research I realised using a permutation generator to solve anagrams is a waste of time! Much better is to use a letter frequency counter and then to compare this with the letter frequency count of words within a dictionary file.

    To illustrate, say I have the word : a,t,r,s
    in its jumbled form. Now I count the number of times each alphabet occurs. So:

    Code:
    a=1, t=1,  r=1,  s=1:
    Now I do the same for every word in the dictionary file and output matches to the screen.

    In this case the dictionary would find two matches, *star* and rats*
    since both words have the same *LETTER FREQUENCY COUNT*. As it turns out, this method to solve anagrams is incredibly quick!
    Hey, that's clever. I'd probably have failed to see the wood for the trees on that one and gone for the permutation solution!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Segmentation fault using recursion to find factorial
    By kapok in forum C++ Programming
    Replies: 4
    Last Post: 02-23-2009, 11:10 AM
  2. Factorial
    By foxman in forum Contests Board
    Replies: 27
    Last Post: 07-11-2008, 06:59 PM
  3. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 12:00 AM
  4. Basic Factorial from 1-10
    By AaA in forum C Programming
    Replies: 20
    Last Post: 05-28-2005, 07:39 AM
  5. factorial output
    By maloy in forum C Programming
    Replies: 1
    Last Post: 03-13-2002, 03:28 PM