论文标题
一种用于计算具有某些尺寸部分的计算设置分区的智能回溯算法
A Smart Backtracking Algorithm for Computing Set Partitions with Parts of Certain Sizes
论文作者
论文摘要
令$α= \ {a_1，a_2，a_3，...，a_n \} $为一组元素，$Δ<n $是非阴性整数，$γ：α\ to \ to \ to \ {0，1，1，2，...，...，n \} $是总映射。然后，我们将$γ$ a \ emph {partition} $α$时，并且仅在α$，$γ（x）\ neq 0 $中的所有$ x \时才称为$α$。此外，我们称$γ$ a $δ$ - \ emph {partition}的$α$时，仅当$γ$是$α$的分区，对于所有$ i \ in \ in \ {1，2，2，3，...，n \} $ >δ$。我们提供了一种非平凡算法，该算法计算所有$δ$ - 分区$α$ in $ω（n）$时间。相反，天真的生成测试算法将计算$ω$ $α$的所有$δ$分区，其中$ω（nb_n）$ time $ b_n $是bell号。
Let $α=\{a_1,a_2,a_3,...,a_n\}$ be a set of elements, $δ< n$ be a non-negative integer, and $Γ: α\to \{0, 1, 2, ..., n\}$ be a total mapping. Then, we call $Γ$ a \emph{partition} of $α$ if and only if for all $x \in α$, $Γ(x) \neq 0$. Further, we call $Γ$ a $δ$-\emph{partition} of $α$ if and only if $Γ$ is a partition of $α$ and for all $i \in \{1, 2, 3, ..., n\}$, $|\{x: Γ(x)=i\}| > δ$. We give a non-trivial algorithm that computes all $δ$-partitions of $α$ in $Ω(n)$ time. On the opposite, a naive generate-and-test algorithm would compute all $δ$-partitions of $α$ in $Ω(nB_n)$ time where $B_n$ is the Bell number.
