Welcome, guest | Sign In | My Account | Store | Cart

The "bell" permutations are those in which only a single inversion of neighbors occurs to generate the next permutation.

Python, 46 lines
 ``` 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.

Robin Becker 10 years, 4 months ago

I made a small modification by removing lines 45-48 and inserting an exit

``````if i is None: break
``````

between lines 28 & 29. I think the algorithm is equivalent and is faster

``````\$ python -mtimeit -s'from bellperm import bell_permutations' 'list(bell_permutations(5))'
100 loops, best of 3: 10 msec per loop
robin@bunyip:~/tmp \$ python -mtimeit -s'from bellperm1 import bell_permutations' 'list(bell_permutations(5))'
100 loops, best of 3: 4.47 msec per loop
robin@bunyip:~/tmp\$ python -mtimeit -s'from bellperm import bell_permutations' 'list(bell_permutations(6))'
10 loops, best of 3: 36.9 msec per loop
robin@bunyip:~/tmp\$ python -mtimeit -s'from bellperm1 import bell_permutations' 'list(bell_permutations(6))'
10 loops, best of 3: 27.5 msec per loop
``````
Chris Smith (author) 10 years, 4 months ago

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.

Robin Becker 10 years, 4 months ago

Sorry if I got the line numbers wrong, your edited version is as I intended (and tested).

Chris Smith (author) 10 years, 3 months ago

No problem. Thanks for checking the modifications. This routine is now part of SymPy, a pure-python computer algebra system.

 Created by Chris Smith on Thu, 19 Dec 2013 (MIT)

### Required Modules

• (none specified)