javascript non-recursive permutation algorithm performance

Question

if (tl;dr) {

Any ideas on how to run this permutation-pattern faster?

} else {

I was wondering if it was possible to write a non-recursive permutation function in javascript that could keep up with the performance of recursive ones (e.g. Heap's algorithm). After a couple of weeks I had an idea which worked out pretty well so far. Here's the explanation https://jsfiddle.net/u68wyvzk/6/

In case the explanation left something unclear, just ask :) }

You might get better answers to this sort of questions at http://codereview.stackexchange.com/ — Idos, Feb 23 '16 at 12:49
thanks for the hint. I just posted it there, too http://codereview.stackexchange.com/questions/120866/javascript-non-recursive-array-permutation-pattern — Michael Teitge, Feb 23 '16 at 13:07

score 0 · Answer 1 · edited May 23 '17 at 12:00

It is always possible to eliminate recursion by manually implementing a stack that would otherwise be implicitly handled by the JavaScript engine. Making the stack explicit allows for some optimizations (as we don't need to store the whole call stack and can eliminate function calls from within inner loops) and is often faster even though the computational complexity remains the same.

See https://stackoverflow.com/a/37580979/1647737 for a performant non-recursive implementation of Heap's algorithm.

javascript non-recursive permutation algorithm performance

1 Answers1