In python, I have a list w of integers, and I would like to efficiently generate all lists of integers such that their sum with weights in w is equal to a certain value a, that is sum([i*j for i,j in zip(w,f)]) == a ie the product of w with f is fixed by a. Here everything is int valued. The brute force version would be to use itertools: from itertools import product a = 20 w = [1,1,3,3] rslt = [] for f in product(range(a), repeat=len(w)): if sum([i*j for i,j in zip(w,f)]) == a: rslt.append(list(f)) print(rslt) This however scales very badly with the value of a. Is there a way of making generating rslt efficiently? I couldn't find a way to impose constraint with itertools directly. Mathematically, starting with a known vector w, I want to find all vectors f such that their dot product is fixed by a. I came up with the idea of a recursive function that compute the difference from a at a given stage of the loop, but I'm having trouble with the implementation. If it's possible to have an implementation that also does arbitrary constraints (e.g. quadratic), that would be fantastic. Continue reading...
