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

Question

Предположим, у вас есть следующий список чисел, {3,6,10,9,13,16,19}, не обязательно в этом порядке. Теперь, не зная, что это набор возможных комбинаций набора {3,6,10}, существует ли алгоритм на любом языке программирования, который можно использовать для эффективного нахождения этой комбинации. В принципе, я хочу восстановить список из общего набора - где все числа включены. Что такое эффективный алгоритм, я не хочу изобретать велосипед, если он уже существует?

Answer 1

Для общего случая, когда может быть любое количество элементов, вот алгоритм 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 числа и ни одно из них не может быть отрицательным:

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

Answer 2

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

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

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

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

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

Edit:

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

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

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

Answer 3

Вот как ты это делаешь. Или, по крайней мере, это наивное решение.

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

Цикл по A. Несмотря на то, что не существует подмножества S, которое складывается в _i , добавляем новое число в S, так что оно делает.

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

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

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