Generating the permutations from a number of Characters

Question

I'm working on a predictive text solution and have all the words being retrieved from a Trie based on input for a certain string of characters, i.e. "at" will give all words formed with "at" as a prefix. The problem that I have now, is that we are also supposed to return all other possibilities from pressing these 2 buttons, Button 2 and button 8 on the mobile phone, which would also give words formed with, "au, av, bt, bu, bv, ct, cu, cv" (most of which won't have any actual words.

Can anyone suggest a solution and how I would go about doing this for calculating the different permutations? (at the moment, I'm prompting the user to enter the prefix (not using a GUI right now)

Answer 1

Welcome to concepts like recursivity and combinatorial-explosion :)

Due to combinatorial explosion, you have to be "smart" about it: if the user wants to enter a legitimate 20 letters word, it is unacceptable for your solution to "hang" trying stupidly tens of millions of possibilities.

So you should only recurse when the trie has at least one entry for your prefix.

Here's a way to generate all prefixes and only recurse when there's a match.

In this example, I faked a trie always saying there's an entry. I made this in five minutes so it can surely be beautified/simplified.

The advantage of such a solution is that it works if the user presses on one, two, three, four or 'n' keys, without needing to change your code.

Note that you probably do not want to add all the words starting with 'x' letters when there are too many. It's up to you to find the strategy that matches best your need (wait for more keypresses to reduce candidates or add most common 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's 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;
    }

Note the recursive call (only when there's a matching prefix).

Here's how you could call it: I faked the user pressing '1', then '2' and then '3' (I faked this in the chars 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() );
}

That example shall create a set containing 36 matches because I "faked" that every prefix is legit and that every prefix leads to exactly one word (and I only added the "word" when it's made of at least two letters). Hence 3*3*3 + 3*3, which gives 36.

You can try the code, it's fully working but you'll have to adapt it of course.

In my fake example (user pressing 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 :)