ip

iterative-permutation

Fast, iterative implementation of Heap's Algorithm for JavaScript

Showing:

Popularity

Downloads/wk

4

GitHub Stars

4

Maintenance

Last Commit

6yrs ago

Contributors

2

Package

Dependencies

0

License

MIT

Type Definitions

Tree-Shakeable

No?

Categories

Readme

iterative-permutation

Fast, iterative implementation of Heap's Algorithm for JavaScript

Overview

This is a non-recursive implementation of Heap's Algorithm that can be used to generate permutations for very large sets of values. Typically recursive solutions generate all sets of values and then return them all at the end. For very large sets it becomes problematic to store all of the permutations in memory. Instead this implementation returns permutations one at a time so they can be processed and discarded if needed.

Installation

npm install iterative-permutation

Example

var Permutation = require('iterative-permutation');

var generator = new Permutation([1, 2, 3]);
while (generator.hasNext()) {
  console.log(generator.next());
}

console.log('finished');

Prints:

[ 1, 2, 3 ]
[ 2, 1, 3 ]
[ 3, 1, 2 ]
[ 1, 3, 2 ]
[ 2, 3, 1 ]
[ 3, 2, 1 ]
finished

Implementation Notes

This implementation keeps track of the algorithm stack in a variable called stack and then updates it with the current index each time a new permutation is calculated. It only uses for loops and simple function calls and has no external dependencies, just regular ol' JavaScript. Why no ES6 generators? Some people have found that generators are a little slow and typically when you need a large number of permutations it's in a hot code path. This implementation tries to be as fast as reasonably possible.

Author

Brian Card: @bmcard

License

MIT License - Copyright 2015 Brian Card

Rate & Review

Great Documentation0
Easy to Use0
Performant0
Highly Customizable0
Bleeding Edge0
Responsive Maintainers0
Poor Documentation0
Hard to Use0
Slow0
Buggy0
Abandoned0
Unwelcoming Community0
100
No reviews found
Be the first to rate

Alternatives

No alternatives found

Tutorials

No tutorials found
Add a tutorial