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

$3

Install via

`` bash
npm install -g multipermute
`

` js
var multipermute = require('multipermute')
multipermute([1,2,3], console.log)
`

` bash
% multipermute A B C
`

$3

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.

` bash
% make
`

Running the bare executable prints usage information:

` bash
% ./multipermute
usage:
./multipermute ...
`

Example usage:

` bash
% ./multipermute a t g c
``

(Note that this is not currently built as the default binary for the npm module, which uses cli.js.)

$3

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.