In this report, we summarize the set partition enumeration problems and thoroughly explain the algorithms used to solve them. These algorithms iterate through the partitions in lexicographic order and are easy to understand and implement in modern high-level programming languages, without recursive structures and jump logic. We show that they require linear space in respect to the set cardinality and advance the enumeration in constant amortized time. The methods discussed in this document are not novel. Our goal is to demonstrate the process of enumerating set partitions and highlight the ideas behind it. This work is an aid for learners approaching this enumeration problem and programmers undertaking the task of implementing it.
翻译:在本报告中,我们总结了所设定的分区查点问题,并透彻地解释了用来解决这些问题的算法。这些算法通过地名录的分隔线循环,很容易以现代高级编程语言理解和实施,没有循环结构和跳跃逻辑。我们显示,它们需要线性空间来说明设定的基点,并在固定的摊销时间内提前查点。本文件讨论的方法并不新颖。我们的目标是展示所设定的分区查点过程,突出其中背后的想法。这项工作有助于学习者处理这个查点问题,程序员则执行这项工作。