2016-08-14 76 views
0

我有10个文本文件,其中包含一列1,-1,0。 我想设置一个总和每个文件的元素的组合。例如,如果我想查看10个文件中的2个文件的所有组合,我将在下面创建2个循环: double sum;算法循环组合

for(int i;i=0;i<n;i++){ 
    for(int j;j=i;j<n;j++){ 
     sum += x[i]+x[j]; 
    } 
} 

另一个例子,如果我想看到更多的是10个文件的3个文件的所有组合,我将创建以下3个回路:

for(int i;i=0;i<n;i++){ 
    for(int j;j=i;j<n;j++){ 
     for(int k;k=j;k<n;k++) 
      sum += x[i]+x[j]+x[k]; 
     } 
    } 
} 

等等,如果我想看组合10个文件中的x个文件,我会创建x个循环。

我的问题是:我正在寻找一种算法,通过选择x来确定循环的数量。如果x = 2,则创建2个循环,如果x = 3,则创建3个循环,如果x = 4,则创建4个循环,或者可能有另一种方法。 非常感谢

+3

如果你有50个文件,50个嵌套循环?这太疯狂了。不用说,有更好的方法,比如使用'std :: next_permutation'和一些逻辑来生成组合(在这里有许多**例子),你需要一个(或两个)循环,而不管项目的数量。 – PaulMcKenzie

+0

@PaulMcKenzie'std :: next_permutation'在这里看起来不是很有用,因为TS需要组合,而不是排列 – alexeykuzmin0

+0

@ alexeykuzmin0 - 你错了。你可以使用'std :: next_permutation'来产生组合,如果你[努力一点]。(http://stackoverflow.com/questions/9430568/generating-combinations-in-c)。诀窍是使用由布尔值组成的控制数组。 – PaulMcKenzie

回答

1

我不确定您提供的代码是否真的有效for (int i;i=0;i<n;++i)最有可能是for (int i=0;i<n;++i)。尽管如此,你正在寻找某种递归。

让我假设你已经将这些数据存储在std::vector中,比我建议创建一个2D变体std::vector<std::vector<int>>

有递归需要2个要素:停止条件和递归:

void function(int &sum, const std::vector<std::vector<int>> &data, std::size_t outerLevel, std::size_t innerLevel, int intermediate) { 
    // Stop condition of recursion, 
    // if we don't have any elements any more, 
    // the intermediate is our final result. 
    if (outerLevel == data.size()) { 
     sum += intermediate; 
     return; 
    } 

    // Recursing 
    const std::vector<int> &subData = data[outerLevel]; 
    for (auto i = innerLevel; i < subData.size(); ++i) { 
     function(sum, 
       data, 
       outerLevel+1, // Go to the next std::vector<int> 
       i,   // Make sure the next inner loop starts at the right index 
       intermedite+subData[i] // Take the intermidiate sum 
       ); 
    } 
} 

// Wrapper to hide itermediate calculation variables 
int functionWrapper(const std::vector<std::vector<int>> &data) { 
    int sum = 0; 
    function(sum, data, 0, 0, 0); 
    return sum; 
} 
0

如果你只是想计算的总和,甚至简单

for (int i = 0; i < n; i++) { 
    for (int j = i; j < n; j++) { 
     sum += x[i] + x[j]; 
    } 
} 

相当于

for (int i = 0; i < n; i++) { 
    sum += (n - i) * x[i]; 
    for (int j = i; j < n; j++) { 
     sum += x[j]; 
    } 
} 

并付出了一些努力

sum += (n + 1) * std::accumulate(std::begin(x), std::end(x), 0); 

和3

const int sumx = std::accumulate(std::begin(x), std::end(x), 0); 
sum += ((n + 1) * (n + 2)/2) * sumx; 
+0

我想感谢你们所有对我的问题回答如此迅速的人。我会研究答案,如果我明白,会回来一段代码。我不得不说,我需要花点时间来确保我理解算法。首先,我将学习PaulMcKenzie – pchiknagi

+0

我也会学习JVApen的答案 – pchiknagi