所有子集共同索引值的總和？

Question

在最近的一個問題中，我必須在大小爲n的數組中的所有可能的子集中對所有可能子集中的所有值求和。

對於例如：如果

array ={1,2,3} 

及其亞羣（K = 2）將（X [I]中，x [j]）其中i <Ĵ

1 2 
1 3 
2 3 
Sum:4,8 

首先我已經使用遞歸（與生成所有子集相同）

int sum_index[k]={0}; 
void sub_set(int array[],int n,int k,int temp[],int q=0,int r=0) 
{ 
    if(q==k) 
    { 
     for(int i=0;i<k;i++) 
      sum_index[i]+=temp[i]; 
    } 
    else 
    { 
     for(int i=r;i<n;i++) 
     { 
      temp[q]=array[i]; 
      sub_set(value,n,k,temp,q+1,i+1); 
     } 
    } 
} 

問題是它需要太多的時間，然後預期。

然後我修改了它......

void sub_set(int array[],int n,int k,int temp[],int q=0,int r=0) 
{ 
    if(q==k) 
    { 
     return; 
    } 
    else 
    { 
     for(int i=r;i<n;i++) 
     { 
      temp[q]=array[i]; 
      sum_index[q]+=temp[q]; //or sum_index[q]+=s[i]; 
      sub_set(value,n,k,temp,q+1,i+1); 
     } 
    } 
} 

仍以太多的時間！

有沒有其他辦法解決這個問題？或者我需要的任何其他修改，我不知道？

Answer 1

不是遍歷可能的子集，而是將它看作一個組合問題。

要使用你的例子k = 2和{1,2,3}，我們來看看結果的第一個值。它有兩個1和一個2.這兩個1對應於可以從{2,3}創建的第一個元素集，而第二個1對應於可以從{3}創建的一個元素集的數量。對於結果的第二個元素中的一個2和兩個3存在類似的排列，並查看出現在要考慮的元素之前的元素的子集。

當k> 2時，事情會變得更加複雜，因爲那麼您將不得不尋找元素被考慮之前和之後的元素組合數量，但基本前提仍然有效。之後乘以可能的子集的數量，然後再計算子集的數量，這將告訴您每個元素對結果有多少貢獻。

Answer 2

std::next_permutation可以幫助：

std::vector<int> sub_set(const std::vector<int>& a, int k) 
{ 
    std::vector<int> res(k, 0); 
    std::vector<bool> p(a.size() - k, false); 
    p.resize(a.size(), true); 

    do 
    { 
     int index = 0; 
     for (std::size_t i = 0; i != p.size(); ++i) { 
      if (p[i]) { 
       res[index++] += a[i]; 
      } 
     } 
    } while (std::next_permutation(p.begin(), p.end())); 
    return res; 
} 

Live Demo

Answer 3

在O溶液（N^2），而不是爲O（n！）：
首先解釋一個微小的（:)）位，那麼一些代碼：

我要在這裏假設你的數組是排序的（如果沒有，首先使用std::sort）。此外，我將使用數組值1,2,3,4 ...在這裏，如果數組包含任意值（如2 8 17），則您必須將其視爲索引（即1 => 2,2 => 8等）

定義：(x choose y)意味着binomial coefficient，它是如何計算的也是在鏈接中。如果你的數組大小爲a，而子集大小爲k，則(a choose k)是排列的數量，例如。 3例如：（1,2），（1,3）和（2,3）。

如果你在每一列之下編寫排列，你想得到每列的總和，如果你知道每一列出現多少次數組元素，這很容易。第一列有多少個1，2和3，第二列有多少（k = 2）。

這裏更大的例子來解釋：（1,2,3,4,5）和所有可能的k's（每一個塊）：

1 
2 
3 
4 
5 

12 
13 
14 
15 
23 
24 
25 
34 
35 
45 

123 
124 
125 
134 
135 
145 
234 
235 
245 
345 

... (didn´t write k=4) 

12345 

Let's介紹列索引，0<=c<k即， c = 0表示第一列，c = 1表示第二列等等;和數組大小s=5。

因此，看例如。在k=3 -block中，您會注意到以1開頭的行（列c = 0）具有k=2的值（2,3,4,5）的所有排列，更一般地，列c中的值x具有全部之後的值爲x+1到s的排列。從x+1到s的值是s-x不同的值，而在c列後面還有k-c-1多列。所以，對於一個值x，你可以計算出((s-x) choose (k-c-1))。
另外，第一列只有1,2,3的值，最後的兩個的數字都不在這裏，因爲在這個列之後有兩個多列。

如果您爲第一列做了這個工作，它會很好地工作。例如。在上述k = 3的第一列中值爲1：
count(x) = ((s-x) choose (k-c-1)) = (4 choose 2) = 6
並且實際上在那裏有6個1。爲每個數組值計算此計數，乘以x*count(x)，並對每個x進行總計，即第一列的結果。

其他列比較難，因爲可以有多個相同編號的「置換塊」。首先，上面的步驟需要進行一些小調整：您需要一個多列數組，每個數組值需要一個乘數，並且每個乘數在開始時爲1.在上面的計算x*count(x)中，取而代之的是x*count(x)*muliplier(x)。

在k=3的例子中，第一列中的1可以跟在2,3,4之後，2可以跟隨3,4和3乘4.因此，第二列的基於3的置換需要兩次計數，四次計數甚至三次;更一般地說很多次，就像前面的colums中有更小的值一樣。將其乘以當前乘數。

... 一些代碼：

#include<iostream> 
#include<vector> 
#include<algorithm> 

using namespace std; 

// factorial (x!) 
unsigned long long fact(unsigned char x) 
{ 
    unsigned long long res = 1; 
    while(x) 
    { 
     res *= x; 
     x--; 
    } 
    return res; 
} 

//binomial coefficient (n choose k) 
unsigned long long binom(unsigned char n, unsigned char k) 
{ 
    if(!n || !k) return 1; 
    return (fact(n)/fact(k))/fact(n-k); 
} 

//just for convenience 
template<class T> void printvector(std::vector<T> data) 
{ 
    for(auto l : data) cout << l << " "; 
    cout << endl; 
} 

std::vector<unsigned long long> calculate(std::vector<int> data, int k) 
{ 
    std::vector<unsigned long long> res(k, 0); //result data 
    std::vector<unsigned long long> multiplier(data.size(), 1); 
    if(k < 1 || k > 255 || data.size() < 1) return res; //invalid stuff 
    std::sort(data.begin(), data.end()); //as described 

    for(int column = 0; column < k; column++) //each column separately 
    { 
     //count what to multiply to the multiplier array later 
     std::vector<unsigned long long> newmultiplier(data.size(), 0); 

     //for each array element in this column 
     for(int x = column; x <= (data.size() + column - k); x++) 
     { 
      //core calculation 
      res[column] += data[x] * multiplier[x] * binom(data.size() - x - 1, k - column - 1); 
      //counting the new multiplier factor 
      for(int helper = x + 1; helper < data.size(); helper++) 
       newmultiplier[helper]++; 
     } 
     //calculating new multiplier 
     for(int x = 0; x < data.size(); x++) 
     { 
      if(newmultiplier[x]) 
       multiplier[x] *= newmultiplier[x]; 
     } 
    } 

    return res; 
} 

int main() { 
    printvector(calculate({1,2,3}, 2)); //output 4 8 
    return 0; 
}