Есть возрастающий вектор из n элементов >= 1. Требуется найти следующее сочетание из 2 элементов с минимальной их суммой за O(1) или за O(log n), зная предыдущее.
Например для вектора {1, 2, 3, 4, 5} это будут сочетания {1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4}, {1, 5}, {2, 5}, {3, 4} и т.д.
Какой алгоритм для этого использовать?
Идейно этот ответ повторяет ответ MBo: приоритетная очередь с парами индексов. Размер очереди N, время инициализации N, время выдачи следующей пары log N. Общее время работы N·log N:
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
void print_pairs(const std::vector<int> &v) {
using pair = std::pair<size_t, size_t>;
const auto sum = [&v](const pair &p) {
return v[p.first] + v[p.second];
};
const auto key = [sum](const pair &p) {
return std::make_pair(sum(p), p.first);
};
const auto cmp = [key](const pair &p1, const pair &p2) {
return key(p2) < key(p1);
};
std::priority_queue<pair, std::vector<pair>, decltype(cmp)> q(cmp);
for (size_t i = 0; i < v.size() - 1; ++i) {
q.push({i, i + 1});
}
while (!q.empty()) {
const pair p = q.top();
q.pop();
std::cout <<
sum(p) << " = " << v[p.first] << " + " << v[p.second] << '\n';
if (p.second < v.size() - 1) {
q.push({p.first, p.second + 1});
}
}
}
int main() {
print_pairs({1, 2, 3, 4, 5});
}
Выложу перебор сочетаний по возрастанию сумм на Python.
Суть такая - в очередь по приоритетам кладём кортежи из суммы соседних элементов, индекса левого и правого. Сравнение происходит по первичному ключу - сумме, а вторичный ключ - левый индекс, что обеспечивает лексикографическое упорядочение.
Первичная закладка в кучу всех левых элементов и сдвиг правых только вправо приводит к тому, что не нужно отслеживать повторы. Размер кучи O(N).
Извлекаем минимальный кортеж из кучи, выводим, сдвигаем правый индекс вправо, обновляем сумму, и вставляем кортеж обратно. Переход к следующему сочетанию - O(logN)
import random, bisect, heapq
n = 6
#a = random.sample(range(1,21), k=n)
#a.sort()
a = [1,2,4,5,6,9]
print(a)
hp = []
for i in range(n-1):
hp.append((a[i]+a[i+1], i, i+1))
heapq.heapify(hp)
while hp:
s,l,r = heapq.heappop(hp)
print(s,l,r,a[l],a[r])
if r < n-1:
heapq.heappush(hp, (a[l]+a[r+1],l,r+1))
[1, 2, 4, 5, 6, 9]
3 0 1 1 2
5 0 2 1 4
6 0 3 1 5
6 1 2 2 4
7 0 4 1 6
7 1 3 2 5
8 1 4 2 6
9 2 3 4 5
10 0 5 1 9
10 2 4 4 6
11 1 5 2 9
11 3 4 5 6
13 2 5 4 9
14 3 5 5 9
15 4 5 6 9
P.S. Задачу "по одной паре получить следующую" попробовал решить с дополнительным массивом "cледующая сумма для данного левого индекса" и поиском левого по этому массиву, а правого по исходному, однако обновление доп. массива должно идти постоянно с начала перечисления, так что тупик.