vendredi 10 juin 2016

Efficient way to get every integer vectors summing to a given number


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