





















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。