Python code for finding reverse average (finding possible value sets that give a certain average)
Question: Background: I am working in Python 3, but if people provide answers in other
programming languages I can still use it. Any suggestions on functions or
efficient algorithm or programming tips would be helpful.

Problem: I have a problem involving sets of four (4) integers and their
average values.

The information given: 1\. the number of integers in the set (4) 2\. the
average of the integers

The information needed: 1\. list of possible values that would result in the
given average

Notes: The number of integers in the set is small so an efficient method of
generating lists shouldn't be that hard, but so far I am stuck. I have been
starting with the sum of the numbers (average * 4), but haven't found the
right way to iterate yet.

EDIT: All integers are non-negative. For my purposes they also aren't bigger
than 8 digits.


Answer: Working with the sum, N, rather than the average.

    
    
    def all_possibilities(N, k=4):
        if k == 1:
            yield (N,)
            return
        for i in xrange(N+1):
            for p in all_possibilities(N-i, k-1):
                yield (i,) + p
    
    
    print list(all_possibilities(5))
    

Produces:

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

In general, there will be choose(N+k-1, k-1) solutions.

A shorter solution leveraging `itertools.combinations` is this:

    
    
    import itertools
    
    def all_possibilities(N, k=4):
        for c in itertools.combinations(range(N + k - 1), k - 1):
            yield tuple(x - y - 1 for x, y in zip(c + (N + k - 1,), (-1,) + c))
    

