While I have seen many permutation recipes on this site, there seems to be no recipe yet which shows how to generate the permutations of a "bag". A bag is like a set but can contain elements more than once.
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | def genbags(P,L = []):
if not max(P):
yield L
else:
for i,x in enumerate(P):
if x:
P[i] -= 1
for b in genbags(P,L+[i]):
yield b
P[i] += 1
def histogram(seq):
L = []
R = []
for i,x in enumerate(seq):
try:
R[L.index(x)] += 1
except ValueError:
R.append(1)
L.append(x)
return L,R
def perm(seq):
L,R = histogram(seq)
for Z in genbags(R):
yield [L[i] for i in Z]
def test():
P = [1],[1],[2],[3]
for b in perm(P):
print b
if __name__=='__main__':
test()
|
I am implementing a bag here simply as a sequence of elements which can be indexed. There is another bag implementation here on activestate, and if my script would be adapted to use this structure, it probably could be written in half the lines of code that it is using now.
The problem is of course that in my sequence, objects could compare as equal when using 'a==b' but could compare as unequal when using 'a is b'. This script compares elements using '=='. I am using the line P = [1],[1],[2],[3] only to show off a bit, demonstrating that my generator can handle mutables (probably its only advantage over the other bag implementation :-). The output of the script should look like:
[[1], [1], [2], [3]] [[1], [1], [3], [2]] [[1], [2], [1], [3]] [[1], [2], [3], [1]] [[1], [3], [1], [2]] [[1], [3], [2], [1]] [[2], [1], [1], [3]] [[2], [1], [3], [1]] [[2], [3], [1], [1]] [[3], [1], [1], [2]] [[3], [1], [2], [1]] [[3], [2], [1], [1]]
