How to generate all the permutations of a multiset?

string algorithm combinations combinatorics backtracking
piyukr picture piyukr · Oct 30, 2013 · Viewed 8.9k times · Source

A multi-set is a set in which all the elements may not be unique.How to enumerate all the possible permutations among the set elements?

Answer

ruggero picture ruggero · Jan 22, 2014

Generating all the possible permutations and then discarding the repeated ones is highly inefficient. Various algorithms exist to directly generate the permutations of a multiset in lexicographical order or other kind of ordering. Takaoka's algorithm is a good example, but probably that of Aaron Williams is better

http://webhome.csc.uvic.ca/~haron/CoolMulti.pdf

moreover, it has been implemented in the R package ''multicool''.

Btw, if you just want the total number of distinct permutations, the answer is the Multinomial coefficient: e.g., if you have, say, n_a elements 'a', n_b elements 'b', n_c elements 'c', the total number of distinct permutations is (n_a+n_b+n_c)!/(n_a!n_b!n_c!)

Related questions

How to generate all permutations of a string in PHP?

I need an algorithm that return all possible combination of all characters in one string. I've tried: $langd = strlen($input); for($i = 0;$i < $langd; $i++){ $tempStrang = NULL; $tempStrang .= substr($input, $i, 1); for($j = $i+1, $k=0; $k < $langd; $k++, $…

Read More
What's the best way to build a string of delimited items in Java?

While working in a Java app, I recently needed to assemble a comma-delimited list of values to pass to another web service without knowing how many elements there would be in advance. The best I could come up with off …

Read More
Reverse the ordering of words in a string

I have this string s1 = "My name is X Y Z" and I want to reverse the order of the words so that s1 = "Z Y X is name My". I can do it using an additional array. I thought …

Read More