Verification and generation of unrefinable partitions
| Autor: | Riccardo Aragona, Lorenzo Campioni, Roberto Civino, Massimo Lauria |
|---|---|
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Mathematics - Number Theory Minimal excludant Computer Science Applications Theoretical Computer Science Integer partitions into distinct part Minimal excludant Algorithms 11P81 05A17 05A19 Signal Processing FOS: Mathematics Mathematics - Combinatorics Integer partitions into distinct part Combinatorics (math.CO) Number Theory (math.NT) Algorithms Computer Science - Discrete Mathematics Information Systems |
| Zdroj: | Information Processing Letters. 181:106361 |
| ISSN: | 0020-0190 |
| Popis: | Unrefinable partitions are a subset of partitions into distinct parts which satisfy an additional unrefinability property. More precisely, being an unrefinable partition means that none of the parts can be written as the sum of smaller integers without introducing a repetition. We address the algorithmic aspects of unrefinable partitions, such as testing whether a given partition is unrefinable or not and enumerating all the partitions whose sum is a given integer. We design two algorithms to solve the two mentioned problems and we discuss their complexity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect