How would you go about finding all possible integer vectors of length n that sum to a given m. I know that in general there is C(m, k) solutions to this problem. For example for n = 4 and m = 2 we have the following solution:
[[2 0 0 0]
[1 1 0 0]
[1 0 1 0]
[1 0 0 1]
[0 2 0 0]
[0 1 1 0]
[0 1 0 1]
[0 0 2 0]
[0 0 1 1]
[0 0 0 2]]
I've written a code that works, but it's far from optimal I think. It's already taking a long time for n = 20 and m = 5. For now I do it recursively by taking the solution for n-1 and adding a 1 everywhere and checking if the solution is not already on the list before adding it.
def outputs(n, m):
outs = np.empty([math.factorial(m + n - 1)/math.factorial(n)/math.factorial(m-1), m], dtype=int)
count = 0
if n == 1:
for i in range(m):
temp = np.zeros(m)
temp[i] = 1
outs[i] = temp.copy()
return outs
output = outputs(n-1, m)
for otp in output:
for i in range(m):
temp = otp.copy()
temp[i] += 1
if temp.tolist() not in outs.tolist():
outs[count] = temp.copy()
count += 1
return outs
The question could be recast by looking for all combination of integers summing to a given number m, and then taking the permutations. But I'm not sure it helps.
Aucun commentaire:
Enregistrer un commentaire