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.

Answer 2

While probably not the most elegant solution, this would work:

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

    L = list(g(3, 5))

    D = []

    i = 1

    while i != len(L):
        for j in xrange(len(L[i])):
            if abs(L[i][j] - L[i-1][j]) > 1:
                D.append(L.pop(i))
                i -= 1
                break
        for d in D:
            ins = True
            for j in xrange(len(L[-1])):
                if abs(L[-1][j] - d[j]) > 1:
                    ins = False
                    break
            if ins:
                L.append(d)
                D.remove(d)
        i += 1

    return L

for i in f(3, 5):
    print i

This prints:

(0, 0, 5)
(0, 1, 4)
(0, 2, 3)
(0, 3, 2)
(0, 4, 1)
(0, 5, 0)
(1, 4, 0)
(2, 3, 0)
(3, 2, 0)
(4, 1, 0)
(5, 0, 0)
(4, 0, 1)
(3, 0, 2)
(2, 0, 3)
(1, 0, 4)
(1, 1, 3)
(2, 1, 2)
(3, 1, 1)
(2, 2, 1)
(1, 2, 2)
(1, 3, 1)

It basically defines g inside of f, as the generator to create the permuations. It then goes through the list of that and checks for each element if the difference (the abs part) between the element in the one sub-list and the one before (not explained very well, I know... But you get it) is greater than 1, and if so removes that list, appends it to D and reduces the index by 1 (which is why I used while instead of for).

Edit: After every check of an element, it goes through D and sees if anything fits to L, and if so, appends it.

It then returns the filtered list.