Подбор слагаемых в numpy на python

Question

Нужна помощь! Имею список из 400 элементов; элементы типа float. Список отсортирован по убыванию, исключены дубли. Хочу получить комбинации слагаемых в numpy.

Пример: Желаемая сумма 880000,

507293+316443+26217+13291+9050+2560+2287+1607+841+411 = 880000,

Вывод должен быть:

507293, 316443, 26217, 13291, 9050, 2560, 2287, 1607;
841, 411 507293, 204591, 66009, 55978, 39236, 4215, 967, 841, 459, 411;
8655560.21, 100778.9, 3660.89;

и тд ...

Т. е. вывести те комбинации чисел, которые дают в сумме 880000. Надеюсь, удалось объяснить понятно. Спасибо.

хорошо, кол-во элементов можно сократить скажем до 50. Покажите как это сделать на таком кол-ве.

Я пытался делать без numpy:

for r in range(1, len(dictA) + 1):

    for keys_combination in itertools.combinations(dictA, r):
        if sum([dictA[key] for key in keys_combination]) == total:
            print({key: dictA[key] for key in keys_combination})

Но работает бесконечно, слышал что можно через Numpy вроде быстрее только не понимаю, как это сделать.

Answer 1

Вот реализация алгоритма из википедии, который ищет подмножество с суммой в интервале [(1-eps)T, T]:

initialize a list L to contain one element 0.

for each i from 1 to n do
    let Ui be a list containing all elements y in L, and all sums xi + y for all y in L.
    sort Ui in ascending order
    make L empty 
    let y be the smallest element of Ui
    add y to L
    for each element z of Ui in increasing order do
        // Trim the list by eliminating numbers close to one another
        // and throw out elements greater than the target sum T.
        if y +  ε T/n < z ≤ T then
            y = z
            add z to L

return the largest element in L.

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

class SetWithSum:
    def __init__(self, s):
        self._items = list(s)
        self._sum = sum(s)
    def add(self, x):
        self._items.append(x)
        self._sum += x
        return self
    def clone(self):
        return SetWithSum(self.items())
    def items(self):
        return self._items
    def sum(self):
        return self._sum
    
    def __repr__(self):
        return f"<{self._sum},{self._items}>"

Алгоритм переписывается на Python один в один:

def find_sum(s, T, eps):
    s = list(sorted(s))
    L = [SetWithSum([s[0]])]
    n = len(s)
    delta = eps*T/n
    for x in s[1:]:
        U = L
        U.extend([ l.clone().add(x) for l in L])
        U = sorted(U, key=SetWithSum.sum)
        y = U[0]
        L = [y]
        for z in U:
            if (y.sum()+delta) < z.sum() and z.sum() <= T:
                y = z
                L.append(y)
    return max(L, key=SetWithSum.sum)

Этот алгоритм близок к полиномиальному, когда T мало по сравнению с суммой всех элементов. В худшем случае, когда T равно сумме всех элементов, а eps около 0, этот алгоритм близок к полному перебору.

Примеры

find_sum([1,2,3,4,5,6,7,8,9,10], 25, eps=1) => <24,[3, 6, 7, 8]>

find_sum([1,2,3,4,5,6,7,8,9,10], 25, eps=0.01) => <25,[1, 2, 4, 5, 6, 7]>

find_sum(range(-10, 10), -1, 0.1) => <-1,[-10, 2, 3, 4]>

Видно, что ищет не самое минимальное подмножество.

Тест на случайном множестве положительных целых чисел размером около 40.

import numpy as np
S = set(np.random.randint(100, size=50))
# len(S) = 38 при одном из запусков
print(find_sum(S, 1000, 0.01))

Результат <1000,[1, 3, 9, 11, 12, 14, 16, 17, 18, 19, 21, 22, 27, 28, 33, 34, 35, 42, 50, 51, 52, 53, 56, 57, 58, 60, 65, 66, 70]>

Если найти не удалось, то возвращается что-нибудь максимально близкое к интервалу [(1-eps)T, T], но не принадлежащее этому интервалу.

Чтобы убедиться в том, что алгоритм не совсем полиномиален, и посмотреть, как алгоритм умеет завешивать компьютер, попробуйте что-нибудь вроде

S = set(np.random.randint(1000, size=150))
# len(S) = 137 при одном из запусков
print(find_sum(S, 30000, 0.001))

У меня i7 считал 18 секунд.

Ограничения реализации

Будет не очень хорошо работать с вещественными числами из-за ошибок округления. Может не найти точную сумму.

БЛОГ НА HUSL

Подбор слагаемых в numpy на python

Ответы (1 шт):

Примеры

Ограничения реализации