Set / Partition (Bibtex)

P410: Enumeration of all paritions in natural order

Input:

An integer $n$.

Output:

All partitions of $n$ in natural order

Complexity:

Comment:

Reference:

[McKay1970] (Bibtex)

P411: Enumeration of all paritions with restriction

Input:

Integers $k$ and $n$.

Output:

All partitions of $n$ whose the smallest part is greater than or equal to $k$.

Complexity:

Comment:

Reference:

[White1970] (Bibtex)

P407: Enumeration of all $k$-partitions of $n$

Input:

Integers $k$ and $n$.

Output:

All $k$-partitions of $n$.

Complexity:

Comment:

Reference:

[Narayana1971] (Bibtex)

P396: Enumeration of all paritions of an integer

Input:

An integer $n$.

Output:

All paritions of $n$.

Complexity:

Comment:

Reference:

[Fenner1980] (Bibtex)

P369: Enumeration of all partitions of a set

Input:

A set $S$.

Output:

All partitions of $S$.

Complexity:

$O(1)$ amortized time per solution.

Comment:

Reference:

[Semba1984] (Bibtex)

P352: Enumeration of all partions of $n$ into integers of size at most $k$

Input:

Integers $n$ and $k$.

Output:

All partions of $n$ into integers of size at most $k$.

Complexity:

Comment:

Reference:

[Savage1989] (Bibtex)

P343: Enumeration of all partitions of a set into a fixed number of blocks

Input:

An integer $k$.

Output:

All partitions of a set into $k$ blocks

Complexity:

$O(1)$ amortized time per solution.

Comment:

Reference:

[Ruskey1993] (Bibtex)

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)

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

Input:

Two integers $n$ and $k$.

Output:

All partitions $D(n, k)$ of $n$ into distinct parts of size at most $k$.

Complexity:

$O(N)$ total time. E.g., $D(10, 5) = \{\{5, 4, 1\}, \{5, 3, 2\}, \{4, 3, 2, 1\}\}$ and $D(11, 4) = \emptyset$.

Comment:

$N$ is the number of partitions.

Reference:

[Rasmussen1995] (Bibtex)

P159: Enumeration of all partition of $\{1, \dots, n\}$ into $k$ non-empty subsets

Input:

An integer $k$.

Output:

All partition of $\{1, \dots, n\}$ into $k$ non-empty subsets.

Complexity:

$O(1)$ time per solution.

Comment:

The number of such partitions is known as the Stirling number of the second kind.

Reference:

[Kawano2005b] (Bibtex)

P258: Enumeration of all integer partitions in (anti-)lexicographical order

Input:

An integer $n$.

Output:

All integer partitions of $n$.

Complexity:

$O(1)$ time per solution on average.

Comment:

Reference:

[Stojmenovic2007] (Bibtex)