Python代码用于寻找反向平均数（找出能得到特定平均值的可能值集）

Question

背景：我在用Python 3编程，不过如果有人用其他编程语言给出答案，我也能用得上。任何关于函数、有效算法或编程技巧的建议都很有帮助。

问题：我遇到了一个关于四个整数及其平均值的问题。

已知信息：

1. 集合中的整数数量（4个）
2. 这些整数的平均值

需要的信息：

1. 能够得到给定平均值的可能值的列表

备注：集合中的整数数量很少，所以生成列表的有效方法应该不难，但到目前为止我还卡住了。我是从这些数字的总和（平均值 * 4）开始的，但还没找到合适的迭代方法。

编辑：所有整数都是非负的。对我来说，它们也不会超过8位数。

Answer 1

假设你真的想要一组（独特的）非负整数，你可以把这些整数命名为 a, b, c, d，并且要满足 a > b > c > d 的关系。同时，这些整数的和必须等于 average * 4。接下来，你可以用一个生成器函数来找出所有可能的组合，代码如下：

def get_4set_with_average(average):
    target_float = average * 4.0
    target = int(target_float)
    if target_float != target or target < 6:
        raise ValueError('No combinations possible')
    for a in xrange(target):
        for b in xrange(a):
            for c in xrange(b):
                for d in xrange(c):
                    if a + b + c + d == target:
                        yield([a, b, c, d])

print list(get_4set_with_average(4))

我们可以通过考虑这四个整数之间的关系来提高效率...

given that...
    a > b > c > d >= 0 and a + b + c + d = target 
it must be that...
    3 <= a <= target - 3,
    2 <= b <= target - a - 1,
    (target - a - b) / 2 < c <= target - a - b

这样我们就得到了：

def get_4set_with_average(average):
    target_float = average * 4.0
    target = int(target_float)
    if target_float != target or target < 6:
        raise ValueError('No combinations possible')
    for a in xrange(3, target - 2):
        for b in xrange(1, min(a, target - a)):
            for c in xrange(int((target - a - b) / 2) + 1, 
                            min(b, target - a - b + 1)): 
                yield([a, b, c, target - a - b - c])

（我对这个进行了简单测试，但没有深入检查 - 你需要自己验证一下。）

毫无疑问，还有更高效的算法，但由于可能的组合数量非常庞大，对于较大的值来说，运行起来会很困难。（即使是 average = 20，在我的机器上也需要很长时间。）

Answer 2

这里我们是用总和N来计算，而不是用平均值。

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))

这样会得到：

[(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)]

通常情况下，会有 choose(N+k-1, k-1) 种解决方案。

一个更简洁的解决方案是利用 itertools.combinations，具体如下：

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))