Looking for Python, NumPy developer

[paymanapi]

Формирование комбинации цен на основе предоставляемых предметов с использованием NumPy


Подробное:

Нужно формировать комбинации чисел до 14 вариантов внутри (то бишь одна комбинация может включать в себя K чисел, возможны повторения).
Нужен лишь один СЛУЧАЙНЫЙ вариант из этих комбинаций, то бишь необязательно генерироваться всевозможные.

Как пример:

K = 2
PRICES = [50, 100, 100, 70, 40, 60, 30, 80]

PRICE = 100

RANDOM VARIANT - [40, 60]
RANDOM VARIANT - [70, 30]

Выполнение этой программы должно быть быстрым, лимиты по времени обозначить реальные не могу, но вы должны предупредить если генерация будет занимать больше 3 секунд, так же стоит отметить что лист с ценами может доходить до 1.000-5.000 вариантов.

 

[voldemort]

import itertools

def AllSubsets(S):
    return itertools.chain(*map(lambda x: itertools.combinations(S, x), range(0, len(S)+1)))


def GetAllPricesWhichSumTo(S, target, K):
    return [subset for subset in AllSubsets(S) if sum(subset) == target and len(subset) == K]

if __name__ == "__main__":
    S =  [50, 100, 100, 70, 40, 60, 30, 80]
    target = 100
    print(GetAllPricesWhichSumTo(S, target,2))

 

[HateMe02]

import itertools

def AllSubsets(S):
    return itertools.chain(*map(lambda x: itertools.combinations(S, x), range(0, len(S)+1)))


def GetAllPricesWhichSumTo(S, target, K):
    return [subset for subset in AllSubsets(S) if sum(subset) == target and len(subset) == K]

if __name__ == "__main__":
    S =  [50, 100, 100, 70, 40, 60, 30, 80]
    target = 100
    print(GetAllPricesWhichSumTo(S, target,2))

itertools.combinations_with_replacement для этой задачи лучше использовать, ну и это просто не может работать быстро ведь генерирует абсолютно все вариации и начиная допустим с 5 уже начинает умирать по скорости, а если S увеличить до 1000-5000 то получается каша уже даже на 4 вариациях.