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