分割成不同深度的对数组

Question

让我们有一个数组a[0],a[1],..,a[6]。我想实现一种算法，它将返回各种深度的各种数量。为了使其更容易理解，认为我有什么返回深度

depth: 1, 
return: 
     (a[6] - a[0]); /*the only possible case for depth = 1*/ 

depth: 2, 
return: 
     (a[1] - a[0]) + (a[6] - a[2]); /*first case*/ 
     (a[2] - a[0]) + (a[6] - a[3]); /*second case*/ 
     (a[3] - a[0]) + (a[6] - a[4]); /*third case*/ 
     (a[4] - a[0]) + (a[6] - a[5]); /*fourth*/ 

depth: 3, 
return: 
     (a[1] - a[0]) + (a[3] - a[2]) + (a[6] - a[4]); /*first case*/ 
     (a[1] - a[0]) + (a[4] - a[2]) + (a[6] - a[5]); /*second case*/ 
     (a[2] - a[0]) + (a[4] - a[3]) + (a[6] - a[5]); /*third case*/ 

这对长7阵列的例子的不同值的算法。我希望算法能够处理任意长度的数组。

我能够使用递归实现算法。以下是C++中的代码

int arr[101]; /*Original array with length N = 100*/ 
set <__int64> Partitions; /*Set, for accumulation of the sum of the partitions*/ 

void get_partitions(int start, int end, int depth, int sum) { 
    if (depth == 1) { 
     sum += (arr[end] - arr[start]); 

     Partitions.insert(sum); 
    } 
    else { 
     int k = end - 2 * (depth - 1); 
     int new_start = start + 1; 

     while (new_start <= k) { 
      int current_sum = (arr[new_start] - arr[new_start - 1]); 

      get_partitions((new_start + 1), end, (depth - 1), (sum + current_sum)); 

      new_start++; 
     } 
    } 
} 

int main() { 
    get_partitions(0, 100, 5, 0); 

    //processing of Partitions 

    return 0; 
} 

此实现有问题。对于大尺寸的数组，程序执行时间太长。

是否有可能改进算法？这个算法还有其他的实现吗？我会很感激的答案。

Answer 1

你可以使用以下方法：

std::vector<std::size_t> initialize(std::size_t depth) 
{ 
    std::vector<std::size_t> res(depth - 1); 

    int i = 1; 
    for (auto& e : res) { 
     e = i; 
     i += 2; 
    } 
    return res; 
} 

bool increase(std::vector<std::size_t>& indexes, std::size_t max) 
{ 
    auto m = max; 
    auto rit = indexes.rbegin(); 
    for (; rit != indexes.rend(); ++rit) { 
     ++*rit; 
     if (*rit + 1 != m) { 
      m = *rit; 
      for (auto it = rit.base(); it != indexes.end(); ++it) { 
       *it = m + 2; 
       m += 2; 
      } 
      if (m < max) { 
       return true; 
      } 
     } 
     m = *rit - 1; 
    } 
    return false; 
} 

Demo。