用于查找反向平均值的Python代码(查找给出某个平均值的可能值集)
用于查找反向平均值的Python代码(查找给出某个平均值的可能值集)
提问于 2013-02-04 02:33:11
背景:我正在使用Python3，但如果人们用其他编程语言提供答案，我仍然可以使用它。任何关于函数、高效算法或编程技巧的建议都会很有帮助。
问题:我有一个问题，涉及四(4)个整数及其平均值的集合。
给定的信息: 1.集合中整数的数量(4) 2.整数的平均值
所需信息: 1.可能导致给定平均值的值的列表
注意:集合中的整数数量很少，所以生成列表的有效方法应该不是很难，但到目前为止我遇到了困难。我一直从数字的总和(平均值* 4)开始，但还没有找到正确的迭代方法。
编辑:所有整数都是非负的。出于我的目的，它们也不超过8位数。
回答 2
Stack Overflow用户
发布于 2013-02-04 04:01:26
使用总和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)]通常，会有(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))Stack Overflow用户
发布于 2013-02-04 05:10:04
假设您确实在寻找一组(唯一的)非负整数，您可以将这些整数命名为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也需要很长时间。)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14675800
复制相关文章
相似问题
腾讯云开发者
