Generating a cyclic 3-Gray code for integer partitions with maximum parts in constant amortized time

Jiahui Shao; Dennis Wong; Ruizhe Zhou; Wei Ke

doi:10.1016/j.procs.2025.10.307

Generating a cyclic 3-Gray code for integer partitions with maximum parts in constant amortized time

Jiahui Shao
, Dennis Wong
, Ruizhe Zhou
, Wei Ke

Faculty of Applied Sciences

Macao Polytechnic University

研究成果: Conference article › 同行評審

摘要

We introduce a novel binary representation to represent integer partitions that offers improved storage efficiency compared to the standard integer representation. We then present a recursive algorithm to generate a cyclic 3-Gray code for integer partitions under this new binary representation with a maximum of k parts. Our algorithm produces each integer partition in constant amortized time per string, using O(n2) space.

原文	English
頁（從 - 到）	261-268
頁數	8
期刊	Procedia Computer Science
卷	273
DOIs	https://doi.org/10.1016/j.procs.2025.10.307
出版狀態	Published - 2025
事件	13th Latin American Algorithms, Graphs, and Optimization Symposium, LAGOS 2025 - Buenos Aires, Argentina 持續時間: 10 11月 2025 → 14 11月 2025

存取文件

10.1016/j.procs.2025.10.307

其它文件與鏈接

Link to publication in Scopus

引用此

@article{0f614fd2a4fa464d899558f7d01dc50c,

title = "Generating a cyclic 3-Gray code for integer partitions with maximum parts in constant amortized time",

abstract = "We introduce a novel binary representation to represent integer partitions that offers improved storage efficiency compared to the standard integer representation. We then present a recursive algorithm to generate a cyclic 3-Gray code for integer partitions under this new binary representation with a maximum of k parts. Our algorithm produces each integer partition in constant amortized time per string, using O(n2) space.",

keywords = "CAT algorithm, Ferrers diagrams, Gray code, Integer partition, integer composition, postorder traversal",

author = "Jiahui Shao and Dennis Wong and Ruizhe Zhou and Wei Ke",

note = "Publisher Copyright: {\textcopyright} 2025 The Authors. Published by Elsevier B.V.; 13th Latin American Algorithms, Graphs, and Optimization Symposium, LAGOS 2025 ; Conference date: 10-11-2025 Through 14-11-2025",

year = "2025",

doi = "10.1016/j.procs.2025.10.307",

language = "English",

volume = "273",

pages = "261--268",

journal = "Procedia Computer Science",

issn = "1877-0509",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Generating a cyclic 3-Gray code for integer partitions with maximum parts in constant amortized time

AU - Shao, Jiahui

AU - Wong, Dennis

AU - Zhou, Ruizhe

AU - Ke, Wei

PY - 2025

Y1 - 2025

N2 - We introduce a novel binary representation to represent integer partitions that offers improved storage efficiency compared to the standard integer representation. We then present a recursive algorithm to generate a cyclic 3-Gray code for integer partitions under this new binary representation with a maximum of k parts. Our algorithm produces each integer partition in constant amortized time per string, using O(n2) space.

AB - We introduce a novel binary representation to represent integer partitions that offers improved storage efficiency compared to the standard integer representation. We then present a recursive algorithm to generate a cyclic 3-Gray code for integer partitions under this new binary representation with a maximum of k parts. Our algorithm produces each integer partition in constant amortized time per string, using O(n2) space.

KW - CAT algorithm

KW - Ferrers diagrams

KW - Gray code

KW - Integer partition

KW - integer composition

KW - postorder traversal

UR - https://www.scopus.com/pages/publications/105023463745

U2 - 10.1016/j.procs.2025.10.307

DO - 10.1016/j.procs.2025.10.307

M3 - Conference article

AN - SCOPUS:105023463745

SN - 1877-0509

VL - 273

SP - 261

EP - 268

JO - Procedia Computer Science

JF - Procedia Computer Science

T2 - 13th Latin American Algorithms, Graphs, and Optimization Symposium, LAGOS 2025

Y2 - 10 November 2025 through 14 November 2025

ER -

Generating a cyclic 3-Gray code for integer partitions with maximum parts in constant amortized time

摘要

存取文件

其它文件與鏈接

指紋

引用此