multipermute
v1.0.0
Published
generate multiset permutations using an efficient loopless algorithm
Downloads
1,137
Maintainers
Readme
multipermute
efficient multiset permutations
Overview
This package contains a method to generate all permutations of a multiset.
The method is described in "Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts." Aaron Williams, 2009. To quote Aaron's website:
"The permutations of any multiset are generated by this simple rule:
- The first symbol a is shifted to the right until it passes over consecutive symbols b c with b < c.
- If a > b, then a is inserted after b; otherwise, if a <= b, then a is inserted after c.
- (If there is no such b c then a is shifted until it passes over the rightmost symbol.)
This result leads to the first O(1)-time / O(1)-additional variable algorithm for generating the permutations of a multiset (see publication in SODA 2009)."
In other words, this algorithm is so awesome that it hurts.
Usage
node.js implementation
Install via
npm install -g multipermute
var multipermute = require('multipermute')
multipermute([1,2,3], console.log)
% multipermute A B C
multipermute.cpp
Included is a C++ library/program which contains a generic function to generate multiset permutations for vectors of any type of object. You can test out the program using strings input from the command line.
% make
Running the bare executable prints usage information:
% ./multipermute
usage:
./multipermute <item1> <item2> ... <itemN>
Example usage:
% ./multipermute a t g c
(Note that this is not currently built as the default binary for the npm module, which uses cli.js.)
multipermute.py
A python library implementation is also included for those who like to indent their code consistently.
multiset combinations
Another repository contains code for multiset combinations: multichoose or on github.