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

Question

This post contains some good python code to find all permutations in a set that sum up to some S. I would like to eliminate output gaps so that no element in the output line is more than 1 different from any adjacent line.

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 suggest some code that will arrange the output in this way?

Answer 1

Here is the simplest adaptation of a naive (“lexically sorted”) solution that I could come up with that preserves the smoothness of the transition 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 begins with (0, 7, 0, 0, 0) .) I assume that there should be some kind of relatively simple fix, but it eludes me at the moment. If I read the question correctly, smoothness and completeness are truly critical requirements.

If you are limited only to n <= 3 , then you can get exactly the required order, getting rid of

  if s % 2: direction = -direction 

But for some reason this seems like a severe restriction.

Answer 2

Although this is probably not the most elegant solution, it will 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 

Fingerprints:

 (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 f , as a generator for creating permutations. Then it scans the list and checks each item if the difference (the abs part) between the item in one sub-list and the previous one (not very well explained, I know ... But you get it) is greater than 1, and if this removes this list, adds it to D and decreases the index by 1 (which is why I used while instead of for ).

Edit: After each check of an element, it goes through D and sees that something is suitable for L , and if so, adds it.

Then it returns the filtered list.