Generate all possible combinations of letters in a word

Question

This is a JavaScript function that returns ALL the possible combinations of whatever word the user enters. I am looking to clean this code up a bit...any and all suggestions are welcome!

  function allAnagrams (word) {
  if (word.length < 2) {
    return [word];
  } else {
      var allAnswers = [];
      for (var i = 0; i < word.length; i++) {
        var letter = word[i];
        var shorterWord = word.substr(0, i) + word.substr(i + 1, word.length - 1);
        var shortwordArray = allAnagrams(shorterWord);
        for (var j = 0; j < shortwordArray.length; j++) {
          allAnswers.push(letter + shortwordArray[j]);
        }
      }
      return allAnswers;
  }
}

allAnagrams("")

Answer 1

I'm going to throw my hat in the ring with the iterative version of Heap's method of generating permutations. It took me a while to get right, as my reference source has a typo in the algorithm -_-.

function swap(chars, i, j) {
    var tmp = chars[i];
    chars[i] = chars[j];
    chars[j] = tmp;
}

function getAnagrams(input) {
    var counter = [],
        anagrams = [],
        chars = input.split(''),
        length = chars.length,
        i;

    for (i = 0; i < length; i++) {
        counter[i] = 0;
    }

    anagrams.push(input);
    i = 0;
    while (i < length) {
        if (counter[i] < i) {
            swap(chars, i % 2 === 1 ? counter[i] : 0, i);
            counter[i]++;
            i = 0;
            anagrams.push(chars.join(''));
        } else {
            counter[i] = 0;
            i++;
        }
    }

    return anagrams;
}

With some sample timings to count the anagrams of "codereview":

$ time node anagrams-heap-iterative.js
3628800

real    0m0.855s
user    0m0.000s
sys     0m0.015s

$ time node anagrams-megawac.js
3628800

real    0m2.286s
user    0m0.000s
sys     0m0.000s

Answer 2

As I worked on a better solution, I figured out a great use for the new JS Iterators & Generators, which I've been reading about. I spent probably 6 hours today fiddling with this solution, and it was worth every minute. You've got some formatting errors, but I'm going to focus completely on performance and leave the formatting to the other reviewers.

---

Running this against a big word will fry your machine

Ok, so maybe that's going a little too far, but seriously, this is an expensive function. I'm no math guru, so I asked this question on Math.SE.

The formula for calculating the number of possible combinations is extremely steep:

Think of it like this:

How many choices do you have for the first letter? Four: 4_ _ _ _.

For the second? Three: 4⋅3 _ _.

Continue like this and you find there are 4⋅3⋅2⋅1=4!=24 choices in total. - MrRicci

Running your function against the word "Encyclopedia" will result in a definite page crash if you run it client-side. So to fix that, I did some thinking.

---

Bear with me - This gets more and more relevant as you read.

I wanted to try generating real words (Having some fun with the codez)

An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once - Wikipeda

When I think of an anagram, I think of the result being real words or phrases. Now, while the purpose of this code review isn't to change the functionality of your code, I couldn't help but want to have some fun with it. So I decided to search for a solution that would allow me to filter out and print any real word anagrams from the result.

Once I finally tracked down a plain text string of ~130,000 English Words to use as my word list, I then needed to convert this list into JS. So I built a function to slice the string at each space, and print out the structure for an object with keyed properties, so that I could very quickly test for the validity of any word via worldList['word'] -> returns true if word is valid.

Printing out a list of 130,000 words into the document body as a JSON string is, like your function, very expensive.

---

... And the relevance:

So here's where your problem meets the one that I invented for myself. How do you process a very expensive loop without crashing a webpage?

In experimenting with the possibilities, I actually discovered a way to allow my function to handle 130,000 words, and your function to sustain a word of any size, by balancing the workload over time.

Loops are sometimes too fast for their own good

Loops are made to be as fast as possible, which is perfect for most of the tasks we use them for in web pages. But if we ask them to handle too much, the browser can't handle it.

So I needed a solution that would allow me to distribute the work load over time, in order to allow the page to handle expensive loops without an issue.

My solution was to build a manual loop via a function that called itself x times, inserting a 1-2ms delay between iterations. This gave the page enough time to handle the loop, which, without the delay, processed words insanely fast until the C's before crashing each time. This worked great for generating my JSON word list structure.

But a delayed loop was extremely tricky to implement in your already recursive function.

I realized then that this is the perfect situation to utilize a solution that I recently read about for JavaScript...

---

JavaScript Iterators and Generators

So, here come JavaScript Iterators & Generators to the rescue.

Now, this review is already a risk of becoming a monster, so instead of explaining Generators, I'm going to quote this soon to be popular answer's one-liner:

TL;DR: the essence of [using a] generator is controlling the suspension of code execution.

And explain simply that generators are in improved way of implimenting iterators.

You can read the rest for yourself in the answer there. If that answer doesn't quite do it for you, you can improve your understanding via the following resources:

• Javascript's Future: Generators

• Generators: a better way to build Iterators

• Generators - MDN

• What Is This Thing Called Generators?

Now, Generators have big potential in the task of avoiding callback hell, but we're going to be using them here not for formatting & structure, but for performance, which is (in my performance-biased opinion) the most elegant reason to use them.

I'm not sure yet whether the generators are the best solution here, but they're the best idea that I have, and this is an excuse to try them out.

---

Your Code With Generators

Working on this solution still. It should work just fine, I just don't have time to finish just yet, and wanted to offer the improved code sooner rather than later. I'll post this solution soon.

Update: A few days later, I haven't finished learning generators, to the point of being able to write this function with them correctly. I will definitely post it here as soon as I figure their syntax out just a little bit better.

---

And Finally, Since Generators are new and not supported everywhere yet.. An improved version of your code without them

Note: My formatting practices are generally my own readability preference rather than best practice. Don't feel obligated to format your code this way.

/* Improved Real Time Anagram Engine */

// Without generators, it's difficult to write this function
// with the capability of processing a word of any length without
// crashing the web browser, so this is written as the original,
// with non-controlled execution speed. Long (9+ char) words may
// crash browser.

function generateAnagrams(word) {

    if (word.length < 2) {

        return [word];

    } else {

        // By declaring all variables outside of the loop,
        // we improve efficiency, avoiding the needless
        // declarations each time.

        var anagrams = [];
        var before, focus, after;
        var shortWord, subAnagrams, newEntry;

        for (var i = 0; i < word.length; i++) {

            before = word.slice(0, i);
            focus = word[i];
            after = word.slice(i + 1, word.length + 1);
            shortWord = before + after;
            subAnagrams = generateAnagrams(shortWord);

            for (var j = 0; j < subAnagrams.length; j++){

                newEntry = focus + subAnagrams[j];
                anagrams.push(newEntry);

            }

        }

        return anagrams;

    }

}

var result = generateAnagrams(word);

By declaring variables outside of the loops, we save significantly, as you'll see in the results. Also, I believe word.slice() performed slightly better than word.substr(). between the two of those optimizations, this code performs better than your original code.

---

And Last but not Least, the performance results!

Original Code : Results updated! Page doesn't crash without logging.

• "code", 4 chars : 24 results, ~1ms
• "coder", 5 chars : 120 results, ~1ms
• "codere", 6 chars : 720 results, ~6ms
• "coderev", 7 chars : 5040 results, ~11ms
• "coderevi", 8 chars : 40,320 results, ~75ms
• "coderevie", 9 chars : 362,880 results, page fail
• "codereview", 10 chars : 3,628,800 results, page fail

Improved Code : Results updated - Page doesn't crash without logging.

• "code", 4 chars : 24 results, ~0.5ms
• "coder", 5 chars : 120 results, ~0.5ms
• "codere", 6 chars : 720 results, ~1.5ms
• "coderev", 7 chars : 5040 results, ~8ms
• "coderevi", 8 chars : 40,320 results, ~53ms
• "coderevie", 9 chars : 362,880 results, ~556ms
• "codereview", 10 chars : 3,628,800 results, ~12725ms

Real-Time with Generators

(Code not complete -- Generators are proving a bit difficult)

I used console.time() to achieve measurements accurate to the nearest millisecond, completing 3-5 trials each, and estimating a general average based on the results. These results will of course vary from machine to machine. The time comparisons are the key to reading benchmarks, not the speeds.

---

Tl;Dr Summary, as promised

Loops are an extremely powerful tool in programming, but they don't handle monster numbers of expensive iterations well in the web browser. Expensive looping functions like this perform perfectly, however, if you distribute the workload over time. One interesting way to do this is to use JS Generators, a new toy available in web stores today, but not necessarily in the local markets, so use with care until JS 2.0 is more widely implemented! By utilizing the power of JS generators, we can manage long-running expensive processes without seeing any performance issues.

Answer 3

I took a look at @jt0dd's code and wondered how we could could handle some more cases. I'll tell you, lets add in a cache layer and precompute the lengths of the resulting arrays!

var generateAnagrams = (function() {
    // precomputed first 20 factorials
    var fact20 = [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000];
    // Substrings seen already which we can cache. Try and avoid stack overflow as much as possible
    var seenStrings = {};

    function generateAnagrams(word) {
        var length = word.length;
        if (length < 2) {
            seenStrings[word] = word;
            return [word];
        }
        var anagrams = Array(fact20[length - 1]);

        // Stuff we'll need along the way
        var before, focus, after;
        var shortWord, subAnagrams, newEntry;
        var idx = 0, j, jlen;

        for (var i = 0; i < length; i++) {
            before = word.slice(0, i);
            focus = word[i];
            after = word.slice(i + 1, word.length + 1);
            shortWord = before + after;
            subAnagrams = seenStrings[shortWord] || generateAnagrams(shortWord);
            for (j = 0, jlen = subAnagrams.length; j < jlen; j++) {
                newEntry = focus + subAnagrams[j];
                anagrams[idx++] = newEntry;
            }
        }
        seenStrings[word] = anagrams;
        return anagrams;
    }

    return function anagrams(word) {
        var computed = generateAnagrams(word);
        // clear cache (going to consume a ton of memory)
        seenStrings = {};
        return computed;
    };
})();

Man that's ugly! I hope all that time wasn't for naught...

Pre-computed hashs

• "code", 4 chars : 24 results, <= 1ms
• "coder", 5 chars : 120 results, <= 1ms
• "codere", 6 chars : 720 results, <= 1ms
• "coderev", 7 chars : 5040 results, <= 3ms
• "coderevi", 8 chars : 40,320 results, <= 18ms
• "coderevie", 9 chars : 362,880 results, 135ms
• "codereview", 10 chars : 3,628,800 results, 2.1 s

Whoopy, we met the challenge. Let's see how much further we can go. codereview is a hard word only duplicate e characters. Lets try something easier for the next go. Lets try "anagramarmy"

... ... ...

Okay, I bit off more than my browser can chew it seems, 40 million string permutations seems to be beyond the limit :(

You'll notice I redesigned the algorithm to avoid stack overflow -- lookups ought to be done outside of the recursion.

We can increase the chance of our algorithm not crashing by making it asynchronous and doing every say 100,000 elements every millisecond to avoid halting.

Answer 4

I made two scripts:

1. The first is fast but can't hold much;
2. The second is slow but can show unlimited results.

Both use prototype I made: fastPush, fastSplit and fastJoin; which are faster than the standard method split and join. Both also use bitwise to check if odd or even, because I know mod is the slowest operation possible on a computer.

The first script beats the fastest result of others by over 750ms (on avarage) on 10chars challenge of permutation.

Array.prototype.swap = function(i, j) {

    var el1 = this[i],
        el2 = this[j];

    this[i] = el2;
    this[j] = el1;

    return this;
};

Array.prototype.fastPush = function(element) {
    this[this.length] = element;
};

String.prototype.fastSplit = function() {

    var array = [];

    for(var i = 0; i < this.length; i++)
        array.fastPush(this[i]);

    return array;
};

Array.prototype.fastJoin = function() {

    var string = "";

    for(var i = 0; i < this.length; i++)
        string += this[i];

    return string;
};

String.prototype.anagrams = function() {

    var i = 1, N = this.length, p = [], anagrams = [], k, word = this.fastSplit();

    anagrams.fastPush(this.toString());

    for(var j = 0; j < N; j++)
        p.fastPush(0);

    while(i < N) {

        if(p[i] < i) {

            k = 0;
            k = (i & 1 != 0) & p[i]; 
            anagrams.fastPush(word.swap(k, i).fastJoin());

            p[i]++;
            i = 1;
        } else {
            p[i] = 0;
            i++
        }
    }

    return anagrams;
};

console.log("asdasdfghj".anagrams());

Anyway this first program has a limit and breaks the page if you try more than 10chars.

The second program (the one below) uses a self invoking function and logs in to the console chunks of 4e4 elements, it clears the anagrams array each time it output a chunk and also clears console.log each 5 chunks (enough to let you see those combinations). To self invoke the function the program uses setZeroTimeout (David Baron's blog) instead of setTimeout because setTimeout is way slower.

(function() {
    var timeouts = [];
    var messageName = "zero-timeout-message";

    // Like setTimeout, but only takes a function argument.  There's
    // no time argument (always zero) and no arguments (you have to
    // use a closure).
    function setZeroTimeout(fn) {
        timeouts.fastPush(fn);
        window.postMessage(messageName, "*");
    }

    function handleMessage(event) {
        if (event.source == window && event.data == messageName) {
            event.stopPropagation();
            if (timeouts.length > 0) {
                var fn = timeouts.shift();
                fn();
            }
        }
    }

    window.addEventListener("message", handleMessage, true);

    // Add the one thing we want added to the window object.
    window.setZeroTimeout = setZeroTimeout;
})();

Array.prototype.swap = function(i, j) {

    var el1 = this[i],
        el2 = this[j];

    this[i] = el2;
    this[j] = el1;

    return this;
};

Array.prototype.fastPush = function(element) {
    this[this.length] = element;
};

String.prototype.fastSplit = function() {

    var array = [];

    for(var i = 0; i < this.length; i++)
        array.fastPush(this[i]);

    return array;
};

Array.prototype.fastJoin = function() {

    var string = "";

    for(var i = 0; i < this.length; i++)
        string += this[i];

    return string;
};

var i = 1, p = [], N, k, chars, anagrams = [], r = 0;

function anagramsGen(word) {

    N = word.length;
    chars = word.fastSplit();
    anagrams.fastPush(word);

    for(var j = 0; j < N; j++)
        p.fastPush(0);

    noLimitWhile();
}

function noLimitWhile() {

    if(i < N) {

        if(p[i] < i) {

            k = 0;
            k = (i & 1 != 0) & p[i]; 
            anagrams.fastPush(chars.swap(k, i).fastJoin());

            if(anagrams.length === 4e4) {

                if(r === 5) {

                    console.clear();
                    r = 0;
                }

                r++;
                console.log(anagrams);
                anagrams = [];
            }

            p[i]++;
            i = 1;
        } else {
            p[i] = 0;
            i++
        }
        setZeroTimeout(noLimitWhile);

    } else {

        console.log(anagrams);
        console.log("Finished");
    }
}

anagramsGen("qwertyuiopas");

Answer 5

Yet another variant (written i C) using a simple counter over the Power Set of all strings.

#include <string.h>
#include <stdio.h>

int main(int argc, char* argv[])
{
  if (argc < 2) return (1);
  char* arg = argv[1];
  int n = 1 << strlen(arg);
  for (int i = 1; i < n; i++) {
    for (int j = 1, l = 0; j <= i; j <<= 1, l++) {
      if (i & j) printf("%c", arg[l]);
    }
    printf("\n");
  }
  return (0);
}

Run with print of all strings:

$ time anagrams codereview > log

real    0m0.002s
user    0m0.000s
sys     0m0.000s

Answer 6

Typed arrays for better performance.

Using the accepted answers method you can triple the performance.

Running the winning answer on my machine gave benchmarked

Mean : 5,564,999µs ±182,246µs 11 samples

And when using typed arrays

Mean : 1,514,112µs ±72,000µs (*) 13 samples

for 3.68 performance increase.

var knownPermutations = [0,0,0,24,120,720,5040,40320,362880,3628800];
function anagramer(input) {
    var counter, chars,length,i,index,tc,n,arraySize,anagrams;
    index = 0;
    length = input.length;
    arraySize = knownPermutations[length-1] * length;
    anagrams = new Uint8Array(arraySize);
    chars = new Uint8Array(length);
    counter = new Uint8Array(length);
    for( i = 0; i < length; i ++){
        chars[i] = input.charCodeAt(i);
    }


    anagrams.set(chars)
    index += length;
    i = 0;
    while (i < length) {
        if (counter[i] < i) {
            tc = chars[i];
            chars[i] = chars[n= (i%2?counter[i]:0)];
            chars[n] = tc;
            counter[i]++;
            i = 0;
            anagrams.set(chars,index)
            index += length;
        } else {
            counter[i] = 0;
            i++;
        }
    }
    return anagrams;
}      

To edge a little more you can predefine the result array to get

 Mean : 1,408,974µs ±25,173µs (*) 24 samples

To improve it up to 3.95 times as quick as the winning answer.