How to find all permutations of positive integers for a given sum and given number of elements.
For example,
Input: sum = 4, number of elements = 2.
Output: (1,3), (3,1), (2,2)
My thinking is, since I know the number of elements is N, I will create N arrays, each from 1 to the sum S-1. So for the example, I will start with two arrays, [1,2,3] and [1,2,3]. Then I will iterate through each array, something like
output = []
for x in array1:
for y in array2:
if x+y == target:
output.append((x,y))
But I don't know how to make it for any N, since that would be variable number of for loops.
Now I have a second idea, I think this works.
import numpy as np
from itertools import combinations
def find_permutations(S,N):
x = np.asarray([x+1 for x in range(S)]*N)
y = [seq for seq in combinations(x,N) if sum(seq)==S]
return list(dict.fromkeys(y)) # remove duplicates
find_permutations(4,2)
[(1, 3), (2, 2), (3, 1)]
But this is extremely slow, since it first create a very long array and find ALL combinations and then filter down. Something like find_permutations(16,16) takes extremely long time but it's obviously just [(1,1,...,1)].
Here's a shorter one (edited to cover border case k <= 1):
def f(sum, k):
if k < 1:
return []
if k == 1:
return [(sum,)]
if k == 2:
return [(i,sum-i) for i in range(1, sum-k+2)]
return [tup[:-1] + ab for tup in f(sum, k-1) for ab in f(tup[-1], 2)]
Test output:
f(2, 0) # []
f(3, 1) # [(3,)]
f(4, 2) # [(1, 3), (2, 2), (3, 1)]
f(5, 3) # [(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)]
The algorithm takes the result for k-1 (i.e., f(sum, k-1), recursively) and applies the same function to decompose all last elements to 2-tuples (i.e., f(tup[-1], 2), again recursively).
Timing comparison:
10.000 repetitions of f(5, 3): 0.07 s
for get_combinations(5, 3): 0.30 s
and for find_permutations(5, 3): 2.35 s
As for speed, I assume it's a similar situation like with Fibonacci sequence, this nested recursion is very inefficient and won't let you much beyond f(20, 10).