Creating permutations from a number of characters
I am working on a smart text solution and get all words retrieved from Trie based on input for a specific character string i.e. "at" will give all words formed with "at" as a prefix. The problem I currently have in myself is that we also have to bring back all other possibilities by pressing these 2 buttons, button 2 and button 8 on the mobile phone, which will also give words formed with "au, av, bt , bu, bv, ct, cu, cv "(most of which won't have any real words.
Can anyone suggest a solution and how would I go about calculating different permutations? (at the moment I am asking the user to enter a prefix (not using the GUI right now)
a source to share
Welcome to concepts like recursion and combinatorial explosion :)
Because of the combinatorial explosion, you have to be smart about this: if a user wants to enter a legitimate 20-letter word, it is not acceptable for your decision to "hang" stupidly using tens of millions of possibilities.
So, you should only overwrite when the trie has at least one entry for your prefix.
All prefixes can be generated here and only recursively when there is a match.
In this example, I faked the trie by always stating the entry there. I did it in five minutes, so it can certainly be decorated / simplified.
The advantage of this solution is that it works if the user presses one, two, three, four, or "n" keys without changing their code.
Note that you probably don't want to add all the words starting with the letters "x" when there are too many of them. It's up to you to find the strategy that best suits your needs (wait for more keystrokes to decrease candidates or add the most frequent matches as candidates, etc.).
private void append( final String s, final char[][] chars, final Set<String> candidates ) {
if ( s.length() >= 2 && doesTrieContainAnyWordStartingWith( s ) ) {
candidates.add( s + "..." ); // TODO: here add all words starting with 's' instead of adding 's'
}
if ( doesTrieContainAnyWordStartingWith( s ) && chars.length > 0 ) {
final char[][] next = new char[chars.length-1][];
for (int i = 1; i < chars.length; i++) {
next[i-1] = chars[i];
}
// our three recursive calls, one for each possible letter
// (you'll want to adapt for a 'real' keyboard, where some keys may only correspond to two letters)
append( s + chars[0][0], next, candidates );
append( s + chars[0][1], next, candidates );
append( s + chars[0][2], next, candidates );
} else {
// we do nothing, it our recursive termination condition and
// we are sure to hit it seen that we're decreasing our 'chars'
// length at every pass
}
}
private boolean doesTrieContainAnyWordStartingWith( final String s ) {
// You obviously have to change this
return true;
}
Notice the recursive call (only if the appropriate prefix is present).
This is how you could call it: I faked the user by hitting "1" then "2" and then "3" (I faked this in the char [] [] array I created):
public void testFindWords() {
// Imagine the user pressed 1 then 2 then 3
final char[][] chars = {
{'a','b','c'},
{'d','e','f'},
{'g','h','i'},
};
final Set<String> set = new HashSet<String>();
append( "", chars, set ); // We enter our recursive method
for (final String s : set ) {
System.out.println( "" + s );
}
System.out.println( "Set size: " + set.size() );
}
This example should create a set containing 36 matches, because I am "fake", that every prefix is legal and that each prefix leads to exactly one word (and I added the word "only" when it made at least two letters). Hence, 3 * 3 * 3 + 3 * 3, which gives 36.
You can try the code, it completely works, but you will have to adapt it of course.
In my fake example (user presses 1,2 then 3), it creates this:
cdh...
afi...
adi...
beg...
cf...
adh...
cd...
afg...
adg...
bei...
ceg...
bfi...
cdg...
beh...
aeg...
ce...
aeh...
afh...
bdg...
bdi...
cfh...
ad...
cdi...
ceh...
bfh...
aei...
cfi...
be...
af...
bdh...
bf...
cfg...
bfg...
cei...
ae...
bd...
Set size: 36
Welcome to real coding :)
a source to share