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

Question

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

Answer 1

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.

Answer 2

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)$.

Answer 3

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.