Modifying Heap's Algorithm for Generating Permutations

Heap's algorithm is a systematic way to cycle through all permutations of N elements "one exchange at a time". For odd N, it's especially neat because the final permutation seems to be only one exchange different from the first permutation.

But, for even N, this wrap-around does not occur. For example, for N=4, the order of permutations is:

So, does anyone have an exchange algorithm which wraps around for even N? If not, how about just for N=4?

Solution

By inspection, one possible sequence that satisfies the constraint would be:

At each step there should be just two elements that are exchanged.

For larger N I would recommend you try to implement the Steinhaus–Johnson–Trotter algorithm which I believe will generate these permutations using just swaps of adjacent elements, and will leave you one swap away from the initial position.

Python code based on rosetta code:

N=4
def s_permutations(seq):
    def s_perm(seq):
        if not seq:
            return [[]]
        else:
            new_items = []
            for i, item in enumerate(s_perm(seq[:-1])):
                if i % 2:
                    new_items += [item[:i] + seq[-1:] + item[i:]
                                  for i in range(len(item) + 1)]
                else:
                    new_items += [item[:i] + seq[-1:] + item[i:]
                                  for i in range(len(item), -1, -1)]
            return new_items

    return [(tuple(item), -1 if i % 2 else 1)
            for i, item in enumerate(s_perm(seq))]

for x,sgn in s_permutations(range(1,N+1)):
    print ''.join(map(str,x))