How to order permutations so that at least 1 element in each permutation differs by exactly 1

Question

This post provides some nice python code to find all the permutations in a set that sum up to some number S. I would like to eliminate the discontinuities in the output so that no one element in a row of output differs by more than 1 from any adjacent row.

Here is the code to generate the output for which I want to order/sort:

def f(n,s):
    if n == 1:
        yield (s,)
    else:
        for i in xrange(s + 1):
            for j in f(n - 1,s - i):
                yield (i,) + j

L = list(f(3,5))

for i in L:
    print i

Output:

(0, 0, 5)
(0, 1, 4)
(0, 2, 3)
(0, 3, 2)
(0, 4, 1)
(0, 5, 0)
(1, 0, 4) <-Bad, 0 transitioned to 4 from one row to the next
(1, 1, 3)
(1, 2, 2)
(1, 3, 1) 
(1, 4, 0)
(2, 0, 3) <-Bad, 4 transitioned to 0 from one row to the next
(2, 1, 2)
(2, 2, 1)
(2, 3, 0)
(3, 0, 2)
(3, 1, 1)
(3, 2, 0)
(4, 0, 1) <-Bad, 2 transitioned to 0 from one row to the next
(4, 1, 0)
(5, 0, 0)

Desired Output:
(0, 0, 5)
(0, 1, 4)
(0, 2, 3)
(0, 3, 2)
(0, 4, 1)
(0, 5, 0)
(1, 4, 0)
(1, 3, 1) 
(1, 2, 2)
(1, 1, 3)
(1, 0, 4)
(2, 0, 3)
(2, 1, 2)
(2, 2, 1)
(2, 3, 0)
(3, 2, 0)
(3, 1, 1)
(3, 0, 2)
(4, 0, 1)
(4, 1, 0)
(5, 0, 0)

Can anyone propose some code which will order the output in this way?

Answer 1

Here is the simplest adaptation of the naive ("lexically sorted") solution that I could come up with which preserves the smoothness-of-transition property and generates all the permutations:

def g(n, s, direction=1):
    if n == 1:
        yield (s,)
    else:
        if direction > 0:
            r = xrange(s + 1)
        else:
            r = xrange(s, -1, -1)
        if s % 2:
            direction = -direction
        for i in r:
            for j in g(n - 1, s - i, direction):
                yield (i,) + j
            direction = -direction

Unfortunately, for odd values of s it does not start with (0,) * (n - 1) + (s,) as desired, but rather (0, s) + (0,) * (n - 2). (So g(5, 7) does not start with (0, 0, 0, 0, 7) but instead starts with (0, 7, 0, 0, 0).) I assume there must be some relatively simple tweak to fix this, but it's eluding me at the moment. If I'm reading the question correctly, the smoothness and completeness are the only truly critical requirements.

If you will only be limited to n <= 3, then you can get exactly the desired ordering by getting rid of

        if s % 2:
            direction = -direction

But somehow that seems like a harsh limitation.