programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Tim Cooke
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Rob Spoor
• Bear Bibeault
Saloon Keepers:
• Jesse Silverman
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• Carey Brown
Bartenders:
• Piet Souris
• Al Hobbs
• salvin francis

# Permutation + comparison program

Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:
I have to find all the permutations with 7 given letters and then I have to find which of these words are in a file (.txt, one word per line): it's like the Scrabble game, which word can I do with my random pulled letters.
I've tried many things but I always have a different problem, how can I do that knowing that I'm a beginner?

Marshal
Posts: 74381
334
• Number of slices to send:
Optional 'thank-you' note:
Welcome to the Ranch

Please show us what you have got so far. What algorithm are you using to find the permutations and combinations?

Nathan Delsein
Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:Welcome to the Ranch
Please show us what you have got so far. What algorithm are you using to find the permutations and combinations?

I have two programs: the first one establishes how to create all the permutations (I think), and the 2nd one gives me the permutations and their quantity for a given word.
I'm French so the descriptions are in French sorry :/
I made the 2nd but I found the 1st on the Internet, that's why I don't understand everything.

Bartender
Posts: 4691
183
• 3
• Number of slices to send:
Optional 'thank-you' note:
Haven't looked at your code, but a method that spawns all permutations of a Collection is always useful. Note that there are n! permutations, if the Collection has size n (if there are no duplicates in that Collection).

However, knowledge of all permutations is not necessary in this case.

Lets say that our given word is "TCA". If we sort the characters, then we get "ACT". Note that "ACT" is a permutation of "TCA". Now suppose our list contains the word "CAT". Since it has the same number of characters as our key, "CAT" might be a candidate. If we sort the characters, we get "ACT". Hey, that is equal to our sorted key, meaning that "ACT" and "CAT" are permutations (or anagrams)! What now?

Nathan Delsein
Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:Haven't looked at your code, but a method that spawns all permutations of a Collection is always useful. Note that there are n! permutations, if the Collection has size n (if there are no duplicates in that Collection).

However, knowledge of all permutations is not necessary in this case.

Lets say that our given word is "TCA". If we sort the characters, then we get "ACT". Note that "ACT" is a permutation of "TCA". Now suppose our list contains the word "CAT". Since it has the same number of characters as our key, "CAT" might be a candidate. If we sort the characters, we get "ACT". Hey, that is equal to our sorted key, meaning that "ACT" and "CAT" are permutations (or anagrams)! What now?

This is a great idea that I hadn't thought of! The only issue for me is that it uses all the given letters: if we give 5 letters, it will give us all the 5 letter words that match, but other words with fewer letters could match too. ex: "acert" --> "trace" but also "cat" or "rat".
After this program, I will have to compare the value of those words with a list like "a=b=r=1,..., k=7,..., z=10" (each character has a value) to find which one has the best value. In this case, a short word could have a higher value than a longer one. That's why I need to find all the words and not those that have the same length as the given one.

Piet Souris
Bartender
Posts: 4691
183
• 1
• Number of slices to send:
Optional 'thank-you' note:
I see.

But that reminds me very much of a program I wrote a couple of months ago. That was a program for my sister, to help het with the game "Wordfeud". This is a print of my user-interface:

In the top-left, you can type the letters that you have (where I use a "?" for a blank tile). If you the npress the button "zoek" (search) then all matching words will be displayed in the right panel, sorted on wordvalue, then on length and then alphabetically.

What I did was: I asort the available letters, as I wrote before, and then I made a full collection 0f all the subsequences of that sorted word.

For instance: say you have available the letters c, a, b, then sorted that would be a, b, c.
Then I form a list of subsequences:

a
ab
ac
abc
b
bc
c

Next, I have this list of words (in my case I downloaded a file with 200.000 Dutch words), and I group all these words with as key the sorted version of each word. So, if the list contains the words "pain" and "anpi", they are both grouped under the key "ainp".

Now, for each word of my subsequences I look if that word is present as key in my grouped table. If so, then all the values that go with that key are valid words.

I also have a table <character, value>, so that I can calculate the value of each word. (Having to deal with these blank tiles that have no value was not easy).

The bottom left panel allows you to specify a pattern that is present on the board. The program then gives all possible words that you can make by putting some of your letters in that pattern. But that is not part of your assignment.

So I have these methods:
String sort(String s)
List<String> getAllSubsequences(String s)
skeg.JPG

Piet Souris
Bartender
Posts: 4691
183
• Number of slices to send:
Optional 'thank-you' note:
Edit: my method getAllSubsequences returns a Set<String>, to eliminate duplicates. For instance, if you have available the letters a, a, b then the subsequences would be:

a
aa
ab
aab
ab
b

and so we would report the values that go with "ab" twice.

Nathan Delsein
Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:
That's exactly what I have to do, even the part for constraint ("E" at 4th place etc.) XD

In my subject, the constraint part considers 2 different criteria:
- a given letter at a given place
- the word length
But I haven't looked at this part for now.

Saloon Keeper
Posts: 1653
61
• Number of slices to send:
Optional 'thank-you' note:
I noticed a Freudian Slip in Piet's GUI, but mostly wanted to say:

The user mostly or entirely used the correct term of permutation.

In most of the work I have done, permutation implies that the ordering matters, combination implies that the ordering doesn't matter.

That is:
A, B, C
A, C, B
B, C, A
B, A, C
C, A, B
C, B, A
are the different permutations of the combination of one A, one B and one C.

I think the phrases are similarly defined in French, but not sure.

On programming problems offered as challenges, it is generally very important to notice this linguistic detail.

Piet Souris
Bartender
Posts: 4691
183
• Number of slices to send:
Optional 'thank-you' note:
Once you have all possibilities, applying a constraint should be straightforward.

Jesse Silverman
Saloon Keeper
Posts: 1653
61
• Number of slices to send:
Optional 'thank-you' note:
A note on Program Structure.

I note that the AnagrammeAlgo class does all of its work in a constructor, which is not always, but often, considered bad form (I used to do this on coding challenges and got eyerolls).

The following code at the end of the constructor leads me to think this was written by a C++ guru "slumming in Java", it looks like it will be helpful in terms of performance but if I recall correctly is almost always a bad idea for things about to go out of scope:

I know the focus here is on the algorithm and getting a correct answer, but I have a lot of people looking at my code and deciding whether or not to hire me, so it would be good to note if that is Cringy in a "C++ expert slumming in Java" way which is what it appeared like to me.

Piet Souris
Bartender
Posts: 4691
183
• Number of slices to send:
Optional 'thank-you' note:

Jesse Silverman wrote:I noticed a Freudian Slip in Piet's GUI

Now you make me curious!

Jesse Silverman wrote:, but mostly wanted to say: (...)

The point I am making is that to check whether BAC is a "permutation" of ABC, you can make all permutations of BAC (and you get the series that you mention) and see whether one of them equals ABC. But much more efficient is to sort both, and see if the sorted versions are equal.

So, if the given word is CBA, then I only need the subsequences of ABC, which is an O(n^2) operation versus an O(n!) operation.

But we digress. Better to wait 'till this topic is done.

Edit: I erred with O(n^2), I erroneously was thinking of subsets instead of subsequences.

Nathan Delsein
Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:
OK, first of all, thank you for your help.
I'm getting closer to what I want, but I keep having a problem with comparing the words I find (anagrams) and the file ("a_dictionnaire.txt").
I'm trying to use "ligne.compareTo(tmp_1)" where tmp_1 is the word from the anagram program (String), and where ligne is defined as :

I'm trying to inject the BufferedReader in the "compareTo" which requires 2 Strings and I understand that a BufferedReader isn't a String but readLine() is a String.
I have 2 questions, is this method usable or not? And where should I put those 3 lines?
For now, I have 2 messages when I compile :
AnagrammeAlgo.java:10: error: unreported exception FileNotFoundException; must be caught or declared to be thrown
AnagrammeAlgo.java:68: error: unreported exception IOException; must be caught or declared to be thrown

PS : my program looks like this :

Piet Souris
Bartender
Posts: 4691
183
• Number of slices to send:
Optional 'thank-you' note:
hi Nathan,

first of all: I tried your code, and although hard to read and understand, it seems to function allright, albeit with a very big disadvantage.

Second: File operations often come with so called checked exceptions. For instance: the specified file may not be found, in which case a "FileNotFoundException" is thrown. You MUST either catch that Exception, or declare the surrounding method to throw that Exception (which is probably easiest for now).

But can you tell us what your plan is with the dictionary? Are you palnning to read all lines?

Nathan Delsein
Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:
For instance: input "ab" => output "a", "ab", "b", "ba". I want to check if those 4 outputs are in the file. To do so, I thought that "compareTo" was good: if "word.compareTo(FileReader)=0" then return the word.
What I have in mind: for each word given by the anagram program, check if it is in the file with a FileReader (line after line, to answer your question). I know this is absolutely not optimal, but I don't know how to do it differently.
If you have better options with some explanation that would be awesome.

Jesse Silverman
Saloon Keeper
Posts: 1653
61
• Number of slices to send:
Optional 'thank-you' note:
The name of this recursively called method:
void Arbre(char [] word, int n, int lg, char [] solution, int taille_solution)

Means "tree" in English, I think?
Even in French, it should likely be made lowercase, to:
void arbre(char [] word, int n, int lg, char [] solution, int taille_solution)

as to most Java programmers it looks like a call to a constructor otherwise, which it of course is not.

Jesse Silverman
Saloon Keeper
Posts: 1653
61
• Number of slices to send:
Optional 'thank-you' note:
Hi Nathan:

You are currently reading the lines from the file inside a loop inside a recursively called function.

It would be better to read all the lines from the file externally to any of that and just be working with whatever you need from there, including possibly:
a simple ArrayList<String> containing the lines, which will actually be single words, if I understand the problem correctly
or
a simple ArrayList<String> containing the lines/words with the letters in each words pre-sorted alphabetically, if you go for the compare sorted approach

Various more complex data structures would help a lot if the list of words to be checked for is very long, such as a HashSet<String> or a trie, but probably these advanced solutions will hurt more than help in getting a first version working.

But I am pretty sure you want to be all done reading anything from the file before starting to recurse on arbre() function.

Piet Souris
Bartender
Posts: 4691
183
• 1
• Number of slices to send:
Optional 'thank-you' note:
What Jesse says:

Put all your permutations in a HashSet<String>, put all the words of your dictionary in another HashSet<String>, and then all that is needed is:

If you look at the API of the Files-class(see this link:  link to the Files class) you see the very conveniet method lines(Path path), that returns all the Strings in the file that is corresponding to the Path. A modern routine could be:

Edit: the java code-tag seems out of order!

Edit 2: in the preview mode, the code looks like monospaced text, but it appears correctly, so it seems.

Nathan Delsein
Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:
I noted everything you said but I'm stuck with my "AnagrammeAlgo"... I think the program is too complicated for me and I couldn't find any other one on the Internet: the only programs I found give anagrams with the same length and not the shorter one.
It seemed simple at first glance: I have all the anagrams, I only need to compare these words with my dictionary file and print the words that are in it. But the realization is not as easy as I thought.
I don't understand my anagram program so I can't modify it, I tried many different things but all failed. In fact, I understand what you are telling me but I can't seem to apply it.
I think my brain has blown up :|

Piet Souris
Bartender
Posts: 4691
183
• 2
• Number of slices to send:
Optional 'thank-you' note:
Hi Nathan,

that algo is indeed very unreadable, and I would simply give up trying to understand it. Instead, I would try to come up with my own routine. Can you think of a way? To make it a tad easier, you may assume that the String is sorted, and we only need the combinations, and not all the permutations (see Jesse post about the difference. If the String is abc, then the sorted combinations are a, ab, ac, abc, b, bc, c while all the permutations would be abc, acb, bac,  bca, cab, cba.

Now, for the combination algo:

the combination consists of three parts: the very first character of s (let's call it a),  all the combinations of s.substring (1) (let's call it F)  and  the cartesian product of a and F. Recursion!  What is the base case?

As a last remark: getting all combinations is O (2^n), the permutations are O (n!), with n being the length of the String. For n  = 3, we have 7 vs 6 possibilities, but for n = 7, we have 127 vs 5040 possibilities. That was my big problem with geting ALL permutations.

Saloon Keeper
Posts: 8760
71
• 1
• Number of slices to send:
Optional 'thank-you' note:
I was looking at the code in the original post and couldn't wrap my head around it. Plus, I don't think it takes into account that letters may appear more than once. This just uses the bit position as the letter position in the string and if it's a '1' then add that character to the StringBuilder.

Piet Souris
Bartender
Posts: 4691
183
• 1
• Number of slices to send:
Optional 'thank-you' note:
I digress, but I must make a correction to what I said in my previous reply. Getting all permutations is not an O(n!) process (or is it?), but even worse. I forgot to take into account that not only do we need all permutations of the full String, but all permutations of the substrings of length 1, length 2, ..., length n (where n is the length of the string).
So that will give us the following number:

nrOfPermutations = sum((n over k) * k!), for k = 1, 2, ..., n.

For instance, if we have ABC, then the length-2 subs are AB, AC, BC, and each comes with 2 permutations, 6 in all.

So, for a length of 7 we get 13699 permutations, versus 127 if we only consider the combinations I was talking about.

Now I'll shut up.

Carey Brown
Saloon Keeper
Posts: 8760
71
• 2
• Number of slices to send:
Optional 'thank-you' note:
You only need combinations. As already mentioned you can take the dictionary word and sort the letters and then compare that string to each combination.

Carey Brown
Saloon Keeper
Posts: 8760
71
• 1
• Number of slices to send:
Optional 'thank-you' note:
To make a normalized map from a dictionary list.

Nathan Delsein
Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:
OK, guys, I have something which works! For now, I have a program that returns all the normalized words makeable with the given letters that are in the file. I have a few questions to understand the program properly:
Line 25: what does "<<" mean?

Line 29: What does "<<=" mean? Which role has "bit" here? I only see an increment for "idx" (I mean idx++ if the vocab isn't good ^^) and not for "bit", I think that "bit" stays "=1" for the entire program, am I wrong?

The rest seems fine!

Next step, how can I find the original words? For instance: the program returns "abc" for "bac" (a french word), but how can I order the letters back to their original position to give me the real word?

Carey Brown
Saloon Keeper
Posts: 8760
71
• 1
• Number of slices to send:
Optional 'thank-you' note:
If you want all the combinations of "ABC" it follows the same patterns as bits in a binary number.
ABC
000 ""
001 "C"
010 "B"
011 "BC"
100 "A"
101 "AC"
110 "AB"
111 "ABC"

Sorry, "idx" is abbreviation for "index" or the character position in the string.

"<<" means shift bits left by N bits which is mathematically equivalent to multiplying by 2.

"<<="  is shift bits and assign so "bit <<= 1" is the same as "bit = bit << 1".

Campbell Ritchie
Marshal
Posts: 74381
334
• Number of slices to send:
Optional 'thank-you' note:

Nathan Delsein wrote:. . . What does "<<=" mean? . . .

The bitwise left shift operator, with and without a combination with assignment.

Carey Brown
Saloon Keeper
Posts: 8760
71
• 1
• Number of slices to send:
Optional 'thank-you' note:

Nathan Delsein wrote:Next step, how can I find the original words? For instance: the program returns "abc" for "bac" (a french word), but how can I order the letters back to their original position to give me the real word?

The way to do this is with a Map<String,Set<String>> where the first String (the key) is "abc" (the normalized characters), and the Set<String> is a Set of words (1 or more) that are real words that are anagrams of the normalized letters.

First, read your entire directory into a List<String> and then create the Map for it with
Later, as you go through your "combinations", take each combination and
Set<String> set = map.get( combination );
If set is null then no matches were found. If set is not null then it contains one or more anagrams.

Nathan Delsein
Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:
I MADE IT !!! Thanks a lot!
Unfortunately, my task isn't finished but this was a hard part for me and I'm happy it's finished.
Now that I have the anagrams that are in the dictionary file, I have to give their value with this list:
• 1 point: "A, E, I, L, N, O, R, S, T, U"
• 2 points: "D, G, M"
• 3 points: "B, C, P"
• 4 points: "F, H, V"
• 8 points: "J, Q"
• 10 points: "K, W, X, Y, Z"
Then, I will have to return all the words with their value + the higher valued word for each length + the higher valued word in general.
I haven't tried anything yet but I was thinking of creating a table with the letters and their values, then calculating the value of each of the letters in a word and adding it all up. Have you got any suggestions, basic errors I need to take care of or anything?

Carey Brown
Saloon Keeper
Posts: 8760
71
• Number of slices to send:
Optional 'thank-you' note:

Nathan Delsein wrote:I MADE IT !!! Thanks a lot!

Excellent!  It would be of help to others with similar problems if you would post your solution(s) back here.

Piet Souris
Bartender
Posts: 4691
183
• Number of slices to send:
Optional 'thank-you' note:
I created a class "WordAndValue", containing a String and the wordfeud value of that String.

Now, suppose we have both a list of all combinations, and the normalized map that Carey showed.

I first made a List<WordAndValue>, call it result. Now, for each combination, if that combination is a key in Carey's map:

calculate the value of that combination.
for each String s in map.get(combination) add a new WordAndValue with arguments s and value to result.

Now we have a list of all the matching words in the dictionary, together with the corresponding values. I then sorted that list first on value, then on the length of the string, and finally alfabetically (see my screenprint in a reply above).

All you need to do then is to print the list.

And finally: Careys algo for getting the combinations is a fine one. Here is an alternative that I described earlier:

Nathan Delsein
Greenhorn
Posts: 10
• Number of slices to send:
Optional 'thank-you' note:

Carey Brown wrote:It would be of help to others with similar problems if you would post your solution(s) back here.

That's what I have at the moment! Note that all annotations are in french to facilitate the explanation of the program to my group mates.

 You showed up just in time for the waffles! And this tiny ad: Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton