A Smart Backtracking Algorithm for Computing Set Partitions with Parts of Certain Sizes

Abstract

Let $\alpha =\{a_1,a_2,a_3,...,a_n\}$ be a set of elements, $\delta <n$ be a non-negative integer, and $\Gamma :\alpha \to \{0,1,2,...,n\}$ be a total mapping. Then, we call $\Gamma$ a \emph{partition} of $\alpha$ if and only if for all $x\in \alpha$, $\Gamma (x)\ne 0$. Further, we call $\Gamma$ a $\delta$-\emph{partition} of $\alpha$ if and only if $\Gamma$ is a partition of $\alpha$ and for all $i\in \{1,2,3,...,n\}$, $|\{x:\Gamma (x)=i\}|>\delta$. We give a non-trivial algorithm that computes all $\delta$-partitions of $\alpha$ in $\Omega (n)$ time. On the opposite, a naive generate-and-test algorithm would compute all $\delta$-partitions of $\alpha$ in $\Omega (n{B}_n)$ time where $B_n$ is the Bell number.