查找與乘子集的總和

比方說，我們已經得到了一套查找與乘子集的總和

{a_1, a_2, a_3, ..., a_n}

的目標是發現我們以下列方式產生了一加：我們發現，其長度爲3的所有子集，然後乘以每個子集的元素（子集{b_1, b_2, b_3}的結果將是b_1*b_2*b_3）。最後，我們總結所有這些產品。

我正在尋找最短的時間執行算法。

例

SET: {3, 2, 1, 2} 

Let S be our sum. 

S = 3*2*1 + 3*2*2 + 2*1*2 + 3*1*2 = 28

來源

2013-11-01 Atomic Tomq

'{3，2，1,2}'是不是一個組* *。這是一個* multiset */*包* – amit

@amit從這個問題看來，它應該被視爲一個集合。 –

@AbhishekBansal不要這麼認爲 - 他計數2次，每個元素的出現次數都很重要 - 而在* set *中則沒有重複次數。 – amit

當允許重複時（如a_1 * a_1 * a_1），計算倍增三元組的總和更容易。這筆錢只是(sum^3)。

由於不允許重複，我們可以將它們相減：(sum^3 - 3*sumsquares*sum)。

但是，上面的公式減去主對角線上的元素3次，而它應該只減一次。需要補償的是：(sum^3 - 3*sumsquares*sum + 2*sumcubes)。

上述公式沒有考慮到3！每個三元組的排列。所以它應該除以3!。

最後，我們有一個線性時間的算法：

給出多集元素的計算總和，平方和，和立方體。
result = (sum^3 - 3*sumsquares*sum + 2*sumcubes)/6

來源

2013-11-01 10:23:19

對不起，沒有得到你的答案。在（a + b + c）^ 3的擴展中還有（a^2）* b這樣的項。你的公式如何減去這些條款？ –

@AbhishekBansal：對於長度爲2（對）的子集，這很容易解釋。我們可以將所有可能的對的產品寫成矩陣。然後爲了得到適當的總和，我們可以將主對角線上方（或下方）的所有元素加在一起。複雜性是O（N^2）。或者，我們可以將每一行相加（它給出a_i *和），然後將所有這些和相加（這給出和^ 2），然後移除主對角線的元素併除以2.現在複雜度爲O（N）。我提出的只是將這種方法推廣到長度爲3的子集。 –

++完整的工作守則C（上Amit的想法跟進）

#include <iostream> 

using namespace std; 

int main() 
{ 
    int s[] = {3, 2, 1, 2}; 

    double sumOfFullList = 0; 
    for (int i = 0; i < 4; i++) 
     sumOfFullList += s[i]; 

    double sum = 0; 

    for (int i = 0; i < 4; i++) { 
     double sumOfList = sumOfFullList - s[i]; 
     sumOfFullList -= s[i]; 
     for (int j = i+1; j < 4; j++) { 
      sumOfList -= s[j]; 
      sum += s[i]*s[j]*(sumOfList); 
      //cout << s[i] << " " << s[j] << " " << sumOfList; 
     } 
    } 

    cout << sum << endl; 
    return 0; 
}

輸出：

來源

2013-11-01 09:06:02

請注意，假設所有正數，'sumOfList'將迅速變爲負數 – amit

@amit oops試圖糾正它。 –

看起來很好（+1） – amit

這裏是一個O(n^2)方法：

sum = SUM(list) 
answer = 0 
for each i from 0 to n: 
    sum -= list[i] 
    remains = sum 
    for each j from i+1 to n: 
     remains -= list[j] 
     answer += list[i] * list[j] * (remains)

它的工作原理，因爲x,y你需要總結x*y*z（所有元素z）每兩個元素，但所有可能z值的總和是SUM(list) - x - y。

所以，與其做：x*y*z1 + x*y*z2 + ... + x*y*z(n-2)，你基本上做x*y*(z1 + ... + z(n-2))

編輯： Editted多計數由於只在「尾巴」不乘，由@AbhishekBansal提及。您需要僅將每個元素與列表的「尾部」相乘，其中尾部是x,y中最後一個元素之後的所有元素。

來源

2013-11-01 09:07:29 amit

哇，沒有想到這一點。 –

我不知何故認爲它可能有重複。 –

@AbhishekBansal TBH，我不確定（重讀後）OP真正需要什麼，他的例子增加了3 * 2 * 1和3 * 1 * 2，但只計算了3 * 2 * 2一次。 – amit

查找與乘子集的總和

回答

相關問題