The "bell" permutations are those in which only a single inversion of neighbors occurs to generate the next permutation.
1 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 35 36 37 38 39 40 41 42 43 44 45 46 | def bell_permutations(n):
"""Return permutations of [0, 1, ..., n - 1] such that each permutation
differs from the last by the exchange of a single pair of neighbors.
The ``n!`` permutations are returned as an iterator. This is an
implementation of the algorithm of Even described at
http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm.
"""
assert type(n) is int and n > 0
if n == 1:
yield (0,)
elif n == 2:
yield (0, 1)
yield (1, 0)
elif n == 3:
for li in [(0, 1, 2), (0, 2, 1), (2, 0, 1), (2, 1, 0), (1, 2, 0), (1, 0, 2)]:
yield li
else:
m = n - 1
op = [0] + [-1]*m
l = list(range(n))
while True:
yield tuple(l)
# find biggest element with op
big = None, -1 # idx, value
for i in range(n):
if op[i] and l[i] > big[1]:
big = i, l[i]
i, _ = big
if i is None:
break # finish if there is no op
# swap it with neighbor in the indicated direction
j = i + op[i]
l[i], l[j] = l[j], l[i]
op[i], op[j] = op[j], op[i]
# if it landed at the end or if the neighbor in the same
# direction is bigger then turn off op
if j == 0 or j == m or l[j + op[j]] > l[j]:
op[j] = 0
# any element bigger to the left gets +1 op
for i in range(j):
if l[i] > l[j]:
op[i] = 1
# any element bigger to the right gets -1 op
for i in range(j + 1, n):
if l[i] > l[j]:
op[i] = -1
|
See discussion here.
I made a small modification by removing lines 45-48 and inserting an exit
between lines 28 & 29. I think the algorithm is equivalent and is faster
Thanks, I think I made the change as you've described. (The numbers you gave suggested that the setting of the -1 should be deleted, but I don't think that's what you intended.) You're right: it is sufficient to conclude that there is no op when not getting a non-None i value.
Sorry if I got the line numbers wrong, your edited version is as I intended (and tested).
No problem. Thanks for checking the modifications. This routine is now part of SymPy, a pure-python computer algebra system.