# Generating all sorted positive integer sequences of given length that sum to a given total

In this thread, a bijective function is requested which, given two positive integers $$n$$ and $$k$$, maps between natural-number identifiers and sequences of $$k$$ positive integers that sum to $$n$$. Due to it being a bijection, one could enumerate the natural numbers from $$1$$ to $$\binom{n+k-1}{k-1}$$ and run the inverse of this function, generating a different sequence each time.

Importantly, in that thread, zero is allowed and order matters: in the example given, $$[0,0,3]$$ has an identifier, and it differs from $$[3,0,0]$$. I now instead want an algorithm that that does not produce permutations of sequences and does not use zeroes, or equivalently, that only produces those sequences of (1) strictly positive integers that (2) are of length $$k$$ and (3) sum to $$n$$ while (4) being sorted.

The lack of zeroes simplifies the amount of possible sequences to $$\binom{n-1}{k-1}$$ (i.e. how many different ways $$k-1$$ dividers can be placed between a sequence of $$n$$ "1" characters). It does not suffice to just generate all $$\binom{n-1}{k-1}$$ sequences and quietly discarding the unsorted ones, because this takes too long. If you run the Python code below for the example of $$n = 11$$ and $$k=6$$, you will see that it takes 252 iterations just to generate the 7 unique ordered sequences of 6 integers that sum to 11. I don't know by what formula you could obtain that 7 explicitly, but I suspect it scales much better w.r.t. $$n$$ and $$k$$ than does $$\binom{n-1}{k-1}$$.

from itertools import combinations

n = 11
k = 6

all_sequences = []
for indices in combinations(range(1,n), r=k-1):
indices = (0,) + indices + (n,)
integers_to_sum = tuple([b-a for a,b in zip(indices[:-1], indices[1:])])
all_sequences.append(integers_to_sum)

print(sorted(all_sequences))
print(len(all_sequences))

all_sequences = set(map(tuple, map(sorted, all_sequences)))
print(sorted(all_sequences))
print(len(all_sequences))

• Can you give your 7 unique ordered sequences of 5 integers that sum to 11? I get 10 of those: $(7,1,1,1,1)$, $(6,2,1,1,1)$, $(5,3,1,1,1)$, $(5,2,2,1,1)$, $(4,4,1,1,1)$, $(4,3,2,1,1)$, $(4,2,2,2,1)$, $(3,3,3,1,1)$, $(3,3,2,2,1)$, $(3,2,2,2,2)$. Commented Sep 5 at 3:12
• @BrianHopkins You're right, it seems that the code above actually produces the results for $k+1$. My sequences were $(1, 1, 1, 1, 1, 6)$, $(1, 1, 1, 1, 2, 5)$, $(1, 1, 1, 1, 3, 4)$, $(1, 1, 1, 2, 2, 4)$, $(1, 1, 1, 2, 3, 3)$, $(1, 1, 2, 2, 2, 3)$, $(1, 2, 2, 2, 2, 2)$ which you're right to point out have $k = 6$ integers, not 5. Oops. The code chooses $k$ dividers rather than $k-1$, so changing r = k to r = k-1 fixes it.
– Mew
Commented Sep 5 at 7:52
• You're looking for what are called "partitions of n into k parts", and yes, the standard algorithm for finding them is something like the recursive one you've given. Commented Sep 5 at 12:51
• @MichaelLugo Thanks, that seems to match up. The given thread is then about compositions whilst I'm looking at integer partitions. Good to have that terminology.
– Mew
Commented Sep 5 at 14:36

I've figured out a recursive algorithm based on Ethan Bolker's suggestion:

from typing import List, Tuple, Dict

IntSequence = Tuple[int,...]

def f(n: int, k: int, upper_limit: int=None,
memoisation: Dict[Tuple[int,int],List[IntSequence]]=None) -> List[IntSequence]:
assert not(n < 0 or k < 0 or (n == 0 and k != 0) or (n != 0 and k == 0))

if memoisation is None:
memoisation = dict()
elif (n,k) in memoisation:
return memoisation[(n,k)]

if k == 0:
return [()]

if not upper_limit:
upper_limit = n-k+1  # Can't take step so large you reach n=0 before k=0.
upper_limit = min(n-k+1, upper_limit)
lower_limit = 1 + (n-1) // k  # Can't take step so small you can't reach n=0 at k=0.

results = []
for step in range(upper_limit, lower_limit-1, -1):  # Largest step first.
paths = f(n-step, k-1, upper_limit=step)
assert len(paths) > 0  # Proof that no redundant calls are made.
for path in paths:
results.append(path + (step,))

memoisation[(n,k)] = results
return results


Any sequence of $$k$$ integers costs one addition plus the cost of the prefixing sequence of $$k-1$$ integers, so if there are $$R(n,k)$$ results given $$n$$ and $$k$$, this algorithm is $$O(k\times R(n,k))$$. The memoisation probably improves the time complexity.

• The memoization is a nice touch. Commented Sep 5 at 14:22

Consider a recursive algorithm for $$f(n,k)$$ that loops on the first summand $$s$$ and calls itself recursively for $$f(n-s, k-1)$$.

• Interesting. I can imagine something like it, yes.
– Mew
Commented Sep 5 at 1:06

As Michael Lugo points out, you're asking about $$p(n,k)$$, the number of partitions of $$n$$ with exactly $$k$$ parts. I believe that the recurrence $$p(n,k) = p(n-1,k-1) + p(n-k,k)$$ was known to Euler. Hindenburg (later in the 1700s) gave an algorithm to generate all the partitions counted by $$p(n,k)$$. Knuth describes and analyzes this in his Art of Computer Programming Vol4A pages 392-293 and 404-405.

• Would you happen to know if this has a closed-form expression? I have no idea what to think of this recurrence or its time complexity as a function of $n$ and $k$.
– Mew
Commented Sep 6 at 17:50
• While there are direct formulas for $p(n,k)$ for small $k$ (up to 5 or so), generally $p(n,k)$ is as complicated as $p(n)$ (e.g., the Hardy-Ramanujan-Rademacher formula). For the complexity, Knuth's "Theorem H" on p405 that I mentioned in the answer establishes that the "cost measure" for Hindenburg's algorithm to generate the partitions counted by $p(n,k)$ is at most $3p(n,k)+k$. Commented Sep 7 at 3:24