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
Diff to Previous Revision
--- revision 1 2013-12-19 15:20:53
+++ revision 2 2013-12-23 02:44:43
@@ -26,6 +26,8 @@
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]
@@ -42,7 +44,3 @@
for i in range(j + 1, n):
if l[i] > l[j]:
op[i] = -1
- # finish when there are no ops
- if not any(i for i in op):
- yield tuple(l)
- break
