Алгоритм для нахождения пары сумм из списка чисел?

Для общего случая, когда может быть любое количество элементов, здесь есть O (q * log (q)) алгоритм, где q - размер входного списка:

1. Сортировать список q в порядке возрастания.
2. Удалите наименьший элемент m и добавьте его в набор результатов. Удалите его из q.
3. Перебрать q. Составьте список чисел, которые мы видели. Если мы видим число, которое есть (число, которое мы уже видели + m), отбросьте его. Это должно содержать половину чисел (все те, которые не включают m).
4. Повторяйте действия с шага 2 до тех пор, пока не будут найдены все числа.

Вот реализация этого алгоритма на Python:

def solve(q):
    q = sorted(q)
    x = []
    while q:
        x.append(q[0])

        s = [False]*len(q)
        s[0] = True
        j = 1

        for i in range(1, len(q)):
            if q[i] == q[0] + q[j]:
                s[i] = True
                j += 1
                while j < len(q) and s[j]:
                    j += 1

        q = [k for k, v in zip(q, s) if not v]
    return x

s = [1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99]
from itertools import combinations
q = list(sum(x) for r in range(1, len(s) + 1) for x in combinations(s, r))
print(solve(q))

Результат:

[1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99]

Исходный ответ:

Предполагая, что в списке всего 3 числа, и что ни одно число не может быть отрицательным:

Два из числа должны быть двумя наименьшими числами в списке. Наибольшее число должно быть суммой всех трех. Путем вычитания можно найти третье число.

1) Найдите два наименьших числа, которые должны быть частью исходного списка.

2) Найдите их сумму, все меньшее в списке должно быть частью исходного списка.

3) Найдите следующую наименьшую сумму и повторяйтесь до тех пор, пока не будут получены все суммы двух чисел.

Каждый раз, когда вы добавляете число в исходный список или находите сумму, удалите его из большого списка.

4) Продолжайте использовать 3 числовые суммы и увеличивайтесь до тех пор, пока большой список не будет пуст.

Изменить:

Для поиска следующей наименьшей суммы требуется отсортированный список номеров. Если список равен A, B, C, D, E, то наименьшая сумма равна A + B, а следующая наименьшая сумма равна A + C.

Производительность настолько ужасна, насколько получается: 2 ^ N, но если я правильно прочитаю ваш вопрос, список содержит ваш первоначальный список и все возможные суммы, что позволит вам значительно повысить производительность.

Например, вы знаете, сколько чисел вы ищете, что означает, что вы знаете, когда вам нужно только одно больше, и поскольку вы также знаете наибольшее число в списке, последнее число является наибольшим числом минус все числа, уже добавленные в ваш исходный список.

Чтобы использовать URL-адрес запроса в качестве ключа кэша, я делаю следующее:

caches_action :index, :cache_path => Proc.new {|c| c.request.url }

Вот как вы это делаете. Или хотя бы его наивное решение.

Сначала номера упорядочиваются по возрастанию. Предполагая, что A - упорядоченный список результатов, а S - набор минимальных чисел, из которых можно построить A.

Loop through A. Пока не существует подмножества S, которое складывается в _i добавить новое число к S так, что это так.

При первой итерации добавляется мин (А). Второе число, вероятно, будет в S. Это достаточно вычислительно интенсивно, потому что для каждого числа, которое вы исследуете в A, вам нужно будет убедиться, что существует подмножество S, которое добавляет к нему и что вы не добавляете число, которое создает подмножество S, которое добавляет к чему-то в A.

Вы можете оптимизировать это несколько, каждый раз, когда вы добавляете число к S, вы отрабатываете все возможные суммы, включая этот новый элемент и удаление их из A. Продолжайте идти, пока вы не опустите A.

Это усложняется, если числа могут быть отрицательными, но вы увидите это, потому что будет должен быть отрицательный элемент A, чтобы это было возможно.

1) Найдите два наименьших числа, они должны быть частью исходный список.

2) Найдите их сумму, все меньшее в списке должно быть частью исходного списка.

3) Найдите следующую наименьшую сумму и повторяйте, пока не будут суммированы все суммы двух чисел.

Каждый раз, когда вы добавляете число в исходный список или находите сумму, удаляйте ее из большого списка.

4) Продолжайте с суммированием трех чисел и продолжайте увеличивать, пока большой список не станет пустым.

Изменить:

Чтобы найти следующую наименьшую сумму, требуется отсортированный список ваших чисел. Если ваш список - A, B, C, D, E, тогда наименьшая сумма - A + B, а следующая наименьшая сумма - A + C.

Производительность настолько ужасна, насколько это возможно: 2 ^ N, но если я правильно понимаю ваш вопрос, список содержит ваш исходный список и все возможные суммы, которые позволят вам значительно повысить производительность.

Например, вы знаете, сколько чисел вы ищете, что означает, что вы знаете, когда вам нужно еще одно, и, поскольку вы также знаете наибольшее число в списке, последнее число - это наибольшее число минус все числа, которые уже были добавлен в ваш исходный список.