#string permutations

Draw something

Draw something is one game I really enjoy playing and don’t feel guilty wasting my time with. That said, occasionally, I have no clues what my friends drew for me which drives me insane. To be honest, I had to visit a cheat site a couple of times. I know it defeats the purpose of the game not to mention it’s not honest but I needed coins to buy more colors, desperately :).

Cheat

Cheat sites ask you to provide two things:

Letters 

The number of letters that make up the answer

and generates all possible combinations of the given letters that can form an English word.

Permutations and word validation

You need to do two things. 

Generate all possible permutations

Filter out permutations that are not English words

String permutation in javascript

Below is a Javascript I wrote to generate all possible permutations within the given length. It took me a while to get this right (and I am still a rookie in javascript world). 

results is an array to store permutations

input is a string from which you pick letters

output is an array that stores a single permutation

used is an array that stores flags to mark used letters

size is integer to pass the length of the word. i.e. size is 4 of the word jean

level is an integer to track the permutation is complete

var permutate = (function() { var results = []; function doPermute(input, output, used, size, level) { if (size == level) { var word = output.join(''); results.push(word); return; } level++; for (var i = 0; i < input.length; i++) { if (used[i]) { continue; } used[i] = true; output.push(input[i]); doPermute(input, output, used, size, level); used[i] = false; output.pop(); } } return { getPermutations: function(input, size) { var chars = input.split(''); var output = []; var used = new Array(chars.length); doPermute(chars, output, used, size, 0); return results; } } })();

Here is the working example on jsfiddle http://jsfiddle.net/jinwolf/Ek4N5/29/

Here are some patterns I used in the example

Singleton pattern

I used the typical Javascript singleton pattern.

Immediate instantiation

by putting parenthesis around the function, the function gets executed immediately and the permutate variable gets instantiated without an extra explicit invokation of the function. 

Closures

The permute object still has access to the private variable results andthe private method doPermute even though it’s been already returned from the main function. It’s called closure in Javascript

Visualize how it works

There is no tree style data structure in this algorithm but if you look at how it builds a permutation, it looks very similar to how Preorder Traversal works in a tree data structure. In other words, it starts from the element itself and moves down to the most left descendant. It keeps drilling down the path until it hits the bottom. Once it reaches the end of the tree, it moves to the right sibling at the same level. After all siblings are visited, it moves up one level and moves to the right sibling. And it keeps doing it until every element in the tree is visited

it starts from ‘a’ (level 1)

it moves one level down and visits ‘b’, skipping ‘a’ since it’s already taken (level 2)

it move one level down and visit ‘c’ skipping ‘a’ and ‘b’ (level 3)

‘c’ is the bottom of the tree and there is no siblings left at that level (level 3)

it moves up one level (level 2)

it visit ‘c’ which is the next sibling of ‘b’ (level 2)

it move one level down and visit ‘b’ skipping ‘a’ and ‘c’ since they are taken (level 3)

no siblings left on level 3 so it moves up one level (level 2)

Again, there is no siblings left on level 2 so it moves up one level (level 1)

Moves to the next sibling ‘b’ on level 1 which is not shown here (level 1)

Repeats the same process