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

The STL provides a way to construct permutations: in <algorithm> we have next_permutation() and friends.

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

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.

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.

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.

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?

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

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.

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!