1#!/usr/local/bin/python3.8 2# -*- coding: utf-8 -*- 3# multipermute.py - permutations of a multiset 4# Erik Garrison <erik.garrison@bc.edu> 2010 5 6""" 7This module encodes functions to generate the permutations of a multiset 8following this algorithm: 9 10Algorithm 1 11Visits the permutations of multiset E. The permutations are stored 12in a singly-linked list pointed to by head pointer h. Each node in the linked 13list has a value field v and a next field n. The init(E) call creates a 14singly-linked list storing the elements of E in non-increasing order with h, i, 15and j pointing to its first, second-last, and last nodes, respectively. The 16null pointer is given by φ. Note: If E is empty, then init(E) should exit. 17Also, if E contains only one element, then init(E) does not need to provide a 18value for i. 19 20[h, i, j] ← init(E) 21visit(h) 22while j.n ≠ φ orj.v <h.v do 23 if j.n ≠ φ and i.v ≥ j.n.v then 24 s←j 25 else 26 s←i 27 end if 28 t←s.n 29 s.n ← t.n 30 t.n ← h 31 if t.v < h.v then 32 i←t 33 end if 34 j←i.n 35 h←t 36 visit(h) 37end while 38 39... from "Loopless Generation of Multiset Permutations using a Constant Number 40of Variables by Prefix Shifts." Aaron Williams, 2009 41""" 42 43class ListElement: 44 def __init__(self, value, next): 45 self.value = value 46 self.next = next 47 def nth(self, n): 48 o = self 49 i = 0 50 while i < n and o.next is not None: 51 o = o.next 52 i += 1 53 return o 54 55def init(multiset): 56 multiset.sort() # ensures proper non-increasing order 57 h = ListElement(multiset[0], None) 58 for item in multiset[1:]: 59 h = ListElement(item, h) 60 return h, h.nth(len(multiset) - 2), h.nth(len(multiset) - 1) 61 62def visit(h): 63 """Converts our bespoke linked list to a python list.""" 64 o = h 65 l = [] 66 while o is not None: 67 l.append(o.value) 68 o = o.next 69 return l 70 71def permutations(multiset): 72 """Generator providing all multiset permutations of a multiset.""" 73 h, i, j = init(multiset) 74 yield visit(h) 75 while j.next is not None or j.value < h.value: 76 if j.next is not None and i.value >= j.next.value: 77 s = j 78 else: 79 s = i 80 t = s.next 81 s.next = t.next 82 t.next = h 83 if t.value < h.value: 84 i = t 85 j = i.next 86 h = t 87 yield visit(h) 88 89if __name__ == '__main__': 90 import sys 91 multiset = sys.argv[1:] 92 if multiset != []: 93 for permutation in permutations(multiset): 94 for item in permutation: 95 print item, 96 print 97 else: 98 print "usage", sys.argv[0], "<multiset>" 99