分割成不同深度的對數組

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。