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.

4 comments

Robin Becker 10 years, 4 months ago  # | flag

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  # | flag

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  # | flag

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  # | flag

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)
Python recipes (4591)
Chris Smith's recipes (3)

Required Modules

  • (none specified)

Other Information and Tasks