Help writing a java anagram solver

I am attempting to write a program that will take a word as input from the user. The program will then find all of the words that can be used from the letters in the word the user inputted. A letter cannot be used twice if it only appears in the inputted word once, so if the inputted word has one o, no word with 2 o's can be formed. There will be a file that the code references that contains a dictionary of words that will be able to be formed. The code must be case insensitive. After a word is inputted, all of the anagrams for the word will be outputted, and the user will be asked for another word. This will continue until the user inputs a blank line.

I'm not sure how to approach writing this code, so any hints or help will be appreciated.

Forget the Java until you have figured out an algorithm (i.e. some procedure) to generate the different permutations in a sequence of characters (the word). This is a simple exercise in logic, not a Java problem (you can probably find such an algorithm online). When you have worked out an algorithm on paper that will generate all the possible arrangements, then you can think about translating it into Java. Once you can generate all the permutations, then you can look up each one in the database.

If you have trouble implementing your algorithm in Java, post up the algorithm and the Java code you're having trouble with, and we'll try to help.

Press on. Nothing in the world can take the place of persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education alone will not; the world is full of educated derelicts. Persistence and determination alone are omnipotent...
C. Coolidge

I have found a code that generates the factorial for the inputted word. I'm guessing the factorials would be contained in an array, and then each factorial would be compared to the list of words to check if it is contained. How, exactly, would this be written into a code though?


This is the code for finding the number of factorials for a word. It will probably have to be modified for when my complete code is written, but its basically what I'll be needing.

class FactorialTest {

public static void main(String args[]) {

int n;
int i;
long result;

for (i=1; i <=10; i++) {
result = factorial(i);
System.out.println(result);
}

} // main ends here


static long factorial (int n) {

int i;
long result=1;

for (i=1; i <= n; i++) {
result *= i;
}

return result;

} // factorial ends here


}

Actually, that code will only generate the number of permutations a word contains. How would I write it so that it produces an array containing all possible permutations of the inputted word?

Quote:

---

Originally Posted by Jamais_Vu

Actually, that code will only generate the number of permutations a word contains. How would I write it so that it produces an array containing all possible permutations of the inputted word?

---

Like I said, either work out the algorithm yourself or find it online. You seem to have decided that a factorial algorithm is an algorithm for generating permutations. It isn't. Why not look for one that does what you want?

Learning how to learn is life's most important skill...
T. Buzan

Actually, simply generating all of the permutations for a word will not be enough, since this only generates permutations of the same length. However, I also need to find the words that contain some, but not all, of the letters in the original word. (i.e. cup would need to return up).

Would I simply need to find a different algorithm that not only generates all permutations of equal length, but also all permutations for all lengths smaller than the original length? This seems like it may be too slow, as the number of permutations for say, a 8 letter word, is already massive.

Quote:

---

Originally Posted by Jamais_Vu

Would I simply need to find a different algorithm that not only generates all permutations of equal length, but also all permutations for all lengths smaller than the original length?

---

That's why I suggested writing your own. It's an interesting exercise, and you can learn about recursion while you're at it.

Quote:

---

This seems like it may be too slow, as the number of permutations for say, a 8 letter word, is already massive.

---

You're right, there are a lot of permutations. So how slow is too slow? How long will your target machine will take to run the algorithm on a given word length?

You don't even have an algorithm yet, so how can you even guess? Computers work pretty fast, but you may find you have to limit the maximum word length. Only running your program will tell you that.

The speed of a non-working program is irrelevant...
S. Heller

would there be a way to break the word into individual characters, and then find the words that use no characters other than those from the divided word? This seems like it would be a more efficient way than attempting to generate all possible permutations of a word.

I would love to simply write my own code, so I am not asking for code to be written for me. However, if you could hint me toward certain commands / strategies that I may use to approach the problem, it would be appreciated.

Quote:

---

Originally Posted by Jamais_Vu

would there be a way to break the word into individual characters

---

A word could be String containing the word characters. If you look at the String API you'll see a number of ways to access individual characters. Alternatively, you could use an array or ArrayList of characters.

Quote:

---

... then find the words that use no characters other than those from the divided word?

---

This is a logic question, not a Java question... I don't know of a simple way to do that. I do know that searching a dictionary can be very fast if you structure it correctly.

Quote:

---

This seems like it would be a more efficient way than attempting to generate all possible permutations of a word.

---

How did you estimate that?

Quote:

---

However, if you could hint me toward certain commands / strategies that I may use to approach the problem, it would be appreciated.

---

I can help with specifically Java problems. Unfortunately I am not an expert in dictionaries and searching algorithms. Maybe someone else here can help. Failing that, Google is your friend. One of the skills a programmer must develop is solving problems of this kind using the resources available.

One can think effectively only when one is willing to endure suspense and to undergo the trouble of searching...
J. Dewey

Ok, I think I have a java specific question that hopefully you will be able to answer.

My new strategy is to take the input word and put it into an array of characters (which I have accomplished). Then, the program will start going through the dictionary of words. The first word will be taken and also put into a character array.

So, the question I have then is how would I go about comparing the two character arrays, to determine if the characters in array 2 are all also in array 1?

After that is accomplished, if it comes back true, then that word would be output, and the program would move on to the next word and perform the same check.

Quote:

---

Originally Posted by Jamais_Vu

So, the question I have then is how would I go about comparing the two character arrays, to determine if the characters in array 2 are all also in array 1?

---

You need to be a bit more specific. Do you just want to know if each character value in one array is present in the other, or if there is a unique character match in one for every character in the other (i.e. if one array has duplicate characters, the other array also has the same duplicates)? Is ordering relevant? is the number of characters relevant?

The Java SDK probably doesn't have a single method tailored to your specific requirement. If you can tell me exactly what your algorithm for comparison is, or, at least the exact specification for the comparison, I may be able to point you to some methods that can help, but sometimes you just have to write your own.

Having said all that, why do you want to put the words into arrays? Have you looked at the String API? String has ways to find individual characters, and to match whole Strings using a regular expression. Unless you already have a comparison algorithm that you know won't use String methods, I suggest you first check to see if String methods can help you.

The point is, you have to decide on the algorithm to do the comparison, then you look to see if there are methods in the SDK that can help. So far, all I've seen is a few vague ideas. Why not work out step by step, on paper, how you would do this task by hand, then when you think you have something that will do the job, translate it into Java. Java won't solve your problem, it's just a way of expressing a solution you have already put together.

The sooner you start to code, the longer the program will take...
R. Carlson