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)]

CodePudding user response：

Here's a recursive solution that will generate tuples that meet the requirements.

def get_combinations(target, num_elements, combinations=None):
    # Initialise an empty list
    if combinations == None:
        combinations = []
    # Calculate the sum of the current list of numbers
    combinations_sum = sum(combinations)
    # Check if the target is reached -> No further recursion necessary
    if (combinations_sum == target and len(combinations) == num_elements):
        # Return this combination of numbers
        yield tuple(combinations)
    else:
        # The combination of numbers doesn't yet total to target value
        # Iterate over each number from 1 to the target value 
        for number in range(1, target   1):
            # Check that neither the target value nor number of elements will be exceeded
            if (combinations_sum   number <= target 
                and len(combinations) < num_elements):
                # Add the number to the list
                new_combo = combinations   [number]
                # Find all solutions for the list
                for c in get_combinations(target, num_elements, new_combo):
                    yield c

Sample output:

[c for c in get_combinations(4, 2)]
> [(1, 3), (2, 2), (3, 1)]

CodePudding user response：

Here's a shorter one:

def f(sum, k):
    if k == 2:
        return [(i,sum-i) for i in range(1, sum-k 2)]
    else:
        result = [[tup[:-1]   ab for ab in f(tup[-1], 2)] for tup in f(sum, k-1)]
        return [item for sublist in result for item in sublist]  # flatten the result

Test output:

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.085 s

for get_combinations(5, 3): 0.300 s

and for find_permutations(5, 3): 2.35 s