P331: Enumeration of all partitions of an integer $n$

P331: Enumeration of all partitions of an integer $n$

Input:

Three integers $n$, $k$, and $\sigma$.

Output:

All partitions $P_\sigma(n, k)$ of $n$ into parts of size at most $k$ in which parts are congruent to $1$ modulo $\sigma$.

Complexity:

$O(N)$ total time. E.g., $P_3(11, 8) = P_3(11, 7) = \left\{ \{7, 4\}, \{7, 1, 1, 1, 1\}, \{4, 4, 1, 1, 1\}, \{4, 1, 1, 1, 1, 1, 1, 1\}, \{1, \dots, 1\}\right\}$.

Comment:

$N$ is the number of partitions.

Reference:

[Rasmussen1995] (Bibtex)