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.