Создание списка, удовлетворяющего линейному целочисленному ограничению в Python ⇐ Python

[Anonymous]

В Python у меня есть список целых чисел w, и я хотел бы эффективно генерировать все списки (неотрицательных) целых чисел так, чтобы их сумма с весами в w была равна определенное значение a, то есть

Код: Выделить всё

 sum([i*j for i,j in zip(w,f)]) == a

т.е. произведение w на f фиксируется a. Здесь все имеет целочисленное значение и положительное или нулевое значение. Версия грубой силы будет использовать itertools:

Код: Выделить всё

from itertools import product

a = 20
w = [1,1,3,3]
rslt = []
for f in product(range(a+1), repeat=len(w)):
if sum([i*j for i,j in zip(w,f)]) == a:
rslt.append(list(f))

print(rslt)

Однако это очень плохо масштабируется со значением . Есть ли способ эффективно генерировать rslt? Я не смог найти способ напрямую наложить ограничение с помощью itertools. Математически, начиная с известного вектора w, я хочу найти все векторы f, для которых их скалярное произведение фиксируется a.
I пришел в голову идея рекурсивной функции, которая вычисляет разницу с на данном этапе цикла, но у меня возникли проблемы с реализацией. Если возможно иметь реализацию, которая также выполняет произвольные ограничения (например, квадратичные), это было бы здорово.

Подробнее здесь: https://stackoverflow.com/questions/792 ... -in-python