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 codereview.stackexchange.com — Idos
– Idos, Commented Feb 23, 2016 at 12:49
thanks for the hint. I just posted it there, too codereview.stackexchange.com/questions/120866/… — Michael Teitge
– Michael Teitge, Commented Feb 23, 2016 at 13:07

Community · Accepted Answer · 2017-05-23 12:00:21Z

0

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.

edited May 23, 2017 at 12:00

CommunityBot

11 silver badge

answered Mar 9, 2017 at 14:38

le_m

20.4k10 gold badges70 silver badges78 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

javascript non-recursive permutation algorithm performance

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related