Let \alpha=\{a_1,a_2,a_3,...,a_n\} be a set of elements, \delta < n be a positive integer, and \Gamma: \alpha \to \{0, 1, 2, ..., n\} be a total mapping. Then, we call \Gamma a partition of \alpha if and only if for all x \in \alpha, \Gamma(x) \neq 0. Further, we call \Gamma a \delta-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. The so-far open issue that we close in this paper is regarding whether the \delta-partitions of \alpha can be computed without computing the partitions of \alpha in advance. As we show in this paper, this issue is not as trivial as it might seem at first sight, especially if any naive generate-and-test procedure has to be avoided. To resolve this issue, we give a formal proof of the correctness of a smart backtracking algorithm that computes the \delta-partitions of \alpha efficiently without a prior construction of the partitions of~\alpha. The algorithm does so by checking (ahead) two properties identifying parts of the search space that are devoid of any \delta-partition of~\alpha .
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 partition of \alpha if and only if for all x \in \alpha, \Gamma(x) \neq 0. Further, we call \Gamma a \delta-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(nB_n) time where B_n is the Bell number .
R
positive
non-negative
R
The so-far open issue that we close in this paper is regarding whether the
We give a non-trivial algorithm that computes all
R
can be computed without computing the partitions of \alpha in advance. As we show in this paper, this issue is not as trivial as it might seem at first sight, especially if any
in \Omega(n) time. On the opposite, a
R
procedure has to be avoided. To resolve this issue, we give a formal proof of the correctness of a smart backtracking algorithm that computes the
algorithm would compute all
R
efficiently without a prior construction of the partitions of~\alpha. The algorithm does so by checking (ahead) two properties identifying parts of the search space that are devoid of any \delta-partition of~\alpha
in \Omega(nB_n) time where B_n is the Bell number