2
$\begingroup$

Given a set $\{1,\ldots,ck\}$, is there a known algorithm to efficiently list all partitions in with $c$ blocks of cardinality $k$?

In The art of computer programming (Fascicle 3B) by Knuth, there's a mention of an algorithm by Ruskey that can list all partitions with $c$ blocks. I could just use this algorithm and discard all partitions that violate the constraint on the equal size of blocks, but I would visit many useless partitions.

Is there a better way?

$\endgroup$
2
$\begingroup$

I don't know if there is a known algorithm, but there is an obvious algorithm: a partition is given by a subset $S$ of $\{1,...,ck\}$ containing the number $1$ and having cardinality $k$, plus a partition of the remaining $(c-1)k$ elements in subsets of cardinality $k$.

This gives a recursive algorithm provided one lists efficiently all subsets of $\{2, ..., ck\}$ having cardinality $k-1$.

Suppose that we have a function $subsets(A, n)$ that lists all the subsets having cardinality n in a set A. We define a function $partitions(A, k)$ that lists all the partitions of $A$ in subsets having cardinality $k$, provided $|A|$ is a multiple of $k$:

function partitions(A, k):
    if A is empty:
        yield the empty partition
    else:
        let a be an arbitrary element of A
        for each S in subsets(A \ {a}, k-1):
            X = S union {a}
            for each P in partitions(A \ X, k):
                yield P union {X}
end
$\endgroup$
  • $\begingroup$ I don't know if I got your idea... let me try to rephrase it: I start by considering $1$ and forming a $k$-block only with elements $>1$ (all of the remaining, in this case). I proceed by considering $2$, etc... Each time I go down a level, I am allowed to form $k$-blocks with the considered element or greater elements, if possible (i.e., if the considered element isn't already in a $k$-block with an upper element. By doing so we shouldn't generate the same partition multiple times. When I have exhausted all the possible $k$-block in one level, I backtrack up and go on with the next $k$-block. $\endgroup$ – Filippo Bistaffa Aug 1 '17 at 10:11
  • $\begingroup$ See my edit with pseudocode. $\endgroup$ – Gribouillis Aug 1 '17 at 11:06
  • $\begingroup$ I implemented this and it seems to work. $\endgroup$ – Filippo Bistaffa Aug 1 '17 at 14:07
  • $\begingroup$ Do you have a link to your implementation? $\endgroup$ – Gribouillis Aug 1 '17 at 14:09
  • $\begingroup$ How do you generate the subsets? In a similar recursive way, I assume. $\endgroup$ – miracle173 Aug 1 '17 at 14:16
3
$\begingroup$

Section 5.10 of Ruskey's book Combinatorial Generation gives a combinatorial Grey code for linear extensions of posets and describes a bijection between set partitions of a chosen shape and linear extensions of a corresponding poset.

Partitions of Given Type

Let $P(n_0, n_1, \ldots, n_t)$ be the set of partitions of the set $\{1, 2, \ldots, n\}$ into blocks of sizes $n_0, n_1, \ldots, n_t$, where $n = n_0 + n_1 + \cdots + n_t$. For example, the partition $\{\{2, 8\}, \{3, 5\}, \{6, 12\}, \{1, 10, 11\}, \{4, 7, 9\}\}$ is in $P(2, 2, 2, 3, 3)$. We have listed the elements in order and the blocks of equal size by the magnitude of their smallest element. The problem of generating the elements of $P$ can be reduced to that of generating the linear extensions of a certain forest poset. The cover relations of the poset consist of chains of sizes $n_i$ together with chains of the maximal elements of the previous chains which have equal values of $n_i$. The linear extension corresponding to our example is $7, 1, 3, 10, 4, 5, 11, 2, 12, 8, 9, 6$. The inverse of this permutation is $2, 8, 3, 5, 6, 12, 1, 10, 11, 4, 7, 9$, which is just our original partition but without the curly braces.

To be a little more precise, assume that the $n_i$ are listed such that $n_0 \le n_1 \le \cdots \le n_t$, and let $s_i = \sum_{j=1}^{i-1} n_i$. The cover relations of the poset are indicated by the $t + 1$ chains $C_i = s_i + 1, s_i + 2, \ldots, s_i + n_i$ and $D_i = s_i + 1, s_{i+1} + 1, \ldots, s_j + 1$, where $n_{i−1} < n_i = n_{i+1} = \ldots = n_j < n_{j+1}$.

The algorithm per se is described in Pruesse and Ruskey, Generating linear extensions fast, SIAM Journal on Computing 23.2 (1994): 373-386.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.