2021/05/16 by Giorgos Stamatelatos, Stamatelatos, Giorgos, Pavlos S. Efraimidis +1 · 1 citation
Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2105.07472
openalex publication_date 2021/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.