Пусть, например, имеется массив a[0], a[1],..,a[6]
. Необходимо реализовать алгоритм, который на вход принимает значение количества пар (параметр depth), а на выходе выдает сумму разности элементов в каждой паре. Чтобы было более понятно, рассмотрим то, что должен вернуть алгоритм для конкретного значения depth
depth: 1,
return:
(a[6] - a[0]); /*единственный возможный случай для depth = 1*/
depth: 2,
return:
(a[1] - a[0]) + (a[6] - a[2]);
(a[2] - a[0]) + (a[6] - a[3]);
(a[3] - a[0]) + (a[6] - a[4]);
(a[4] - a[0]) + (a[6] - a[5]);
depth: 3,
return:
(a[1] - a[0]) + (a[3] - a[2]) + (a[6] - a[4]);
(a[1] - a[0]) + (a[4] - a[2]) + (a[6] - a[5]);
(a[2] - a[0]) + (a[4] - a[3]) + (a[6] - a[5]);
Выше был приведен пример для массива размерности 7. Я хочу реализовать алгоритм для массива произвольной размерности.
На данный момент мне удалось реализовать этот алгоритм с помощью рекурсии. Ниже приведен код на C++ (Для примера взят массив длины 100)
int arr[101]; /*Исходный массив длины 100*/
set <__int64> Partitions; /*Множество для накопления суммы разности элементов пар*/
void get_partitions(int start, int end, int depth, int sum) {
//start - индекс массива, с которого начинаем перебор вариантов
//end - индекс последнего элемента массива
//depth - текущее значение параметра количества пар
//sum - накопленная разность
//Если depth == 1, то получаем финальный sum и записываем в Partitions
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);
//Обрабатываем множество Partitions
return 0;
}
Данная реализация имеет одну серьезную проблему. Для массива большой размерности, время выполнения программы слишком долгое.
Можно ли улучшить этот алгоритм? Возможно эта задача уже известная. Есть ли другие способы реализовать данный алгоритм? Буду благодарен за ответы.
UPD:
Массив a[0], a[1],..,a[N]
разбивается на d
пар:
(a[0], a[i_1]), (a[i_1 + 1], a[i_2]), (a[i_2 + 1], a[i_3]), ..., (a[i_{d-1}], a[N])
,
где d
- параметр depth. Индексы i_j
должны удовлетворять условиям:
0 < i_1 < (i_1 + 1) < i_2 < (i_2 + 1) < i_3 < ... < i_{d-1} < N
.
a[4]-a[2]
, а при 2 -(a[5]-a[3]) + (a[4]-a[0])
?