Have ideas to improve npm?Join in the discussion! »

    iterative-permutation

    1.0.0 • Public • Published

    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

    Install

    npm i iterative-permutation

    DownloadsWeekly Downloads

    4

    Version

    1.0.0

    License

    MIT

    Last publish

    Collaborators

    • avatar