8

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?

Community
  • 1
  • 1
MatchPoint
  • 81
  • 3
  • 1
    sounds like gray code [http://en.wikipedia.org/wiki/Gray_code] .. except not binary – TehTris Dec 18 '13 at 17:46
  • lol after reading the article on wiki i just posted, it has something VERY similar to what you want, and a code example – TehTris Dec 18 '13 at 17:48
  • 1
    @TehTris: Your link is broken. Click help to see how it's done ;) – jazzpi Dec 18 '13 at 17:51
  • http://en.wikipedia.org/wiki/Gray_code Woops.... lol – TehTris Dec 18 '13 at 17:52
  • Yes, strikingly similar to a Gray code sequence except for the fact the row elements are in decimal instead of binary. Maybe something on the Gray code wiki could be leverage to devise efficient ordering algorithm for these types of permutations. – MatchPoint Dec 18 '13 at 20:02
  • The algorithm you seek is given by J.M. as pseudocode at https://mathoverflow.net/a/279874 – Lori Dec 31 '22 at 01:06

2 Answers2

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.

John Y
  • 14,123
  • 2
  • 48
  • 72
0

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.

jazzpi
  • 1,399
  • 12
  • 18
  • This solution is compliant with the requirement that a least one element in each row has a delta of 1 from any adjacent row; however, we lost valuable permutations when we popped, but did not reinsert. A proper algorithm will generate output exactly as shown in the "Desired output" block in the problem description. – MatchPoint Dec 18 '13 at 19:57
  • @BrianMullen: Didn't see the desired output, updated post to fix that :) – jazzpi Dec 18 '13 at 20:38
  • We don't lose any permutations. But, order of the permutations in the output matters. In the "desired output" the left most element is always increasing and elements to the right always smoothly vacillate from one extreme to another (without causing the sum to exceed S). If these permutations are used as inputs to a function, the outputs of the function should also generate a some smooth wave form (which is my goal). If the discrete output from my function can be modeled as a smooth wave form, it will be easier for my algorithm to find local maximums (gradient ascent). – MatchPoint Dec 18 '13 at 22:41