How to generate all the permutations of a multiset?

Question

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?

Overleap

I'm assuming that you know how to generate the permutations for a unique set. For a multi-set, sort the set, and just keep the same logic with one change, discard the permutation for next number in set if it is same as the current number. – Chiropody

Answer 1

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!)

Pairoar

The link is now broken. The algorithm with implementations in multiple languages is now at this link. – Judicator

Answer 2

This is my translation of the Takaoka multiset permutations algorithm into Python (available here and at repl.it):

def msp(items):
  '''Yield the permutations of `items` where items is either a list
  of integers representing the actual items or a list of hashable items.
  The output are the unique permutations of the items given as a list
  of integers 0, ..., n-1 that represent the n unique elements in
  `items`.

  Examples
  ========

  >>> for i in msp('xoxox'):
  ...   print(i)

  [1, 1, 1, 0, 0]
  [0, 1, 1, 1, 0]
  [1, 0, 1, 1, 0]
  [1, 1, 0, 1, 0]
  [0, 1, 1, 0, 1]
  [1, 0, 1, 0, 1]
  [0, 1, 0, 1, 1]
  [0, 0, 1, 1, 1]
  [1, 0, 0, 1, 1]
  [1, 1, 0, 0, 1]

  Reference: "An O(1) Time Algorithm for Generating Multiset Permutations", Tadao Takaoka
  https://pdfs.semanticscholar.org/83b2/6f222e8648a7a0599309a40af21837a0264b.pdf
  '''

  def visit(head):
      (rv, j) = ([], head)
      for i in range(N):
          (dat, j) = E[j]
          rv.append(dat)
      return rv

  u = list(set(items))
  E = list(reversed(sorted([u.index(i) for i in items])))
  N = len(E)
  # put E into linked-list format
  (val, nxt) = (0, 1)
  for i in range(N):
      E[i] = [E[i], i + 1]
  E[-1][nxt] = None
  head = 0
  afteri = N - 1
  i = afteri - 1
  yield visit(head)
  while E[afteri][nxt] is not None or E[afteri][val] < E[head][val]:
      j = E[afteri][nxt]  # added to algorithm for clarity
      if j is not None and E[i][val] >= E[j][val]:
          beforek = afteri
      else:
          beforek = i
      k = E[beforek][nxt]
      E[beforek][nxt] = E[k][nxt]
      E[k][nxt] = head
      if E[k][val] < E[head][val]:
          i = k
      afteri = E[i][nxt]
      head = k
      yield visit(head)

Clutter

Answer 3

sympy provides multiset_permutations.

from the doc:

>>> from sympy.utilities.iterables import multiset_permutations
>>> from sympy import factorial
>>> [''.join(i) for i in multiset_permutations('aab')]
['aab', 'aba', 'baa']
>>> factorial(len('banana'))
720
>>> sum(1 for _ in multiset_permutations('banana'))
60

Dote

Answer 4

There are O(1) (per permutation) algorithms for multiset permutation generation, for example, from Takaoka (with implementation)

Abscind

Answer 5

Optimisation of smichr's answer, I unzipped the nxts to make the visit function more efficient with an accumulate() (the map() is faster than a list comprehension and it seemed shallow and pedantic to have to nest it in a second one with a constant index)

from itertools import accumulate
def msp(items):
    def visit(head):
        '''(rv, j) = ([], head)
        for i in range(N):
            (dat, j) = E[j]
            rv.append(dat)
        return(rv)'''
        #print(reduce(lambda e,dontCare: (e[0]+[E[e[1]]],nxts[e[1]]),range(N),([],head))[0])
        #print(list(map(E.__getitem__,accumulate(range(N-1),lambda e,N: nxts[e],initial=head))))
        return(list(map(E.__getitem__,accumulate(range(N-1),lambda e,N: nxts[e],initial=head))))
    u=list(set(items))
    E=list(sorted(map(u.index,items)))
    N=len(E)
    nxts=list(range(1,N))+[None]
    head=0
    i,ai,aai=N-3,N-2,N-1
    yield(visit(head))
    while aai!=None or E[ai]>E[head]:
        beforek=(i if aai==None or E[i]>E[aai] else ai)
        k=nxts[beforek]
        if E[k]>E[head]:
            i=k
        nxts[beforek],nxts[k],head = nxts[k],head,k
        ai=nxts[i]
        aai=nxts[ai]
        yield(visit(head))

Here are the test results (the second has (13!/2!/3!/3!/4!)/10! = 143/144 times as many permutations but takes longer due to being more of a multiset, I suppose), mine seems 9% and 7% faster respectively:

cProfile.run("list(msp(list(range(10))))")
cProfile.run("list(msp([0,1,1,2,2,2,3,3,3,3,4,4,4]))")
original:
43545617 function calls in 28.452 seconds
54054020 function calls in 32.469 seconds
modification:
39916806 function calls in 26.067 seconds
50450406 function calls in 30.384 seconds

I have insufficient reputation to comment upon answers, but for an items input list, Martin Böschen's answer has time complexity the product of the factorials of the number of instances of each element value times greater, or

reduce(int.__mul__,map(lambda n: reduce(int.__mul__,range(1,n+1)),map(items.count,set(items))))

This can grow large quickly when computing large multisets with many occurrences. For instance, it will take 1728 times longer per permutation for my second example than my first.

Psychotic

Answer 6

You can reduce your problem to enumerate all permutations of a list. The typcial permutation generation algorithm takes a list and don't check if elements are equal. So you only need to generate a list out of your multiset, and feed it to your permutation generating algorithm.

For example, you have the multiset {1,2,2}.

You transform it to the list [1,2,2].

And generate all permutations, for example in python:

import itertools as it
for i in it.permutations([1,2,2]):
   print i

And you will get the output

(1, 2, 2)
(1, 2, 2)
(2, 1, 2)
(2, 2, 1)
(2, 1, 2)
(2, 2, 1)

The problem is, that you get some permutations repeatedly. A simple solution would be just to filter them out:

import itertools as it
permset=set([i for i in it.permutations([1,2,2])])
for x in permset:
   print x

Output:

(1, 2, 2)
(2, 2, 1)
(2, 1, 2)

Lodicule

Here permutations are getting repeated. – Chiropody