用於查找反向平均值的Python代碼（查找可給出某個平均值的可能值集）

背景：我在Python 3中工作，但如果人們在其他編程語言中提供答案，我仍然可以使用它。任何有關函數或高效算法或編程技巧的建議都會有所幫助。用於查找反向平均值的Python代碼（查找可給出某個平均值的可能值集）

問題：我有一個涉及四（4）個整數集合及其平均值的問題。

的信息給出： 1.整數集合中的數（4） 2.平均整數的

所需的信息：這將導致在給定的可能的值的 1.列表平均值

注：集合中的整數數量很小，因此生成列表的有效方法應該不那麼困難，但到目前爲止我被卡住了。我一直從數字總和（平均值* 4）開始，但還沒有找到正確的迭代方式。編輯：所有整數都是非負數。爲我的目的，他們也不會超過8位數字。

2013-02-03 Michael Blum

歡迎來到Stack Overflow！看起來你希望我們爲你寫一些代碼。儘管許多用戶願意爲遇險的編碼人員編寫代碼，但他們通常只在海報已嘗試自行解決問題時才提供幫助。證明這一努力的一個好方法是包含迄今爲止編寫的代碼，示例輸入（如果有的話），期望的輸出和實際獲得的輸出（控制檯輸出，堆棧跟蹤，編譯器錯誤 - 無論是適用）。您提供的細節越多，您可能會收到的答案就越多。 –

我會將我的代碼添加到問題中。 –

必須暗含一些限制，例如所有整數都應該是正數。否則，可能有多種組合。 –

使用總和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))

來源

2013-02-03 20:01:25

由於這個問題涉及到一組*整數，我認爲它們必須是唯一的。但這個問題應該可以澄清這一點。 – Stuart

假設你真的找一個設定的（唯一的）非負整數，你能說出整數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])

（我測試過這一點，但不是徹底的 - 你將需要檢查它。）

毫無疑問，有更高效的算法，但可能的組合數量很大，這使得難以運行大數值。（即使平均值= 20，我的機器也需要很長時間。）

來源

2013-02-03 21:10:04 Stuart

用於查找反向平均值的Python代碼（查找可給出某個平均值的可能值集）

回答

相關問題