Prefix-Reversal Gray Codes for Combinations and Multiset Permutations

We ask whether all distinct arrangements of a fixed collection of symbols can be visited once by reversing initial segments, with one final reversal returning to the start. Requiring a cycle to contain at least three distinct arrangements, such a listing exists exactly when at least three distinct symbols occur, or when two occur and each occurs at least twice. For binary words, we construct smaller paths with entrance and exit choices that allow them to be joined. For general multisets, we carry colours through binary tours and join the resulting cycles. For the canonical binary cycle, we compute the successor from the current word in linear time. We also stream the reversal lengths with constant worst-case control delay after linear initialization. Both algorithms use linear working space. Control delay measures the work to choose and emit the next reversal length, excluding physical reversal, copying and printing of the word.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-19
DOI
https://doi.org/10.5281/zenodo.24380923
Primary Topic
Advanced Combinatorial Mathematics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Prefix-Reversal Gray Codes for Combinations and Multiset Permutations

Ariel Elboim
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

Prefix-Reversal Gray Codes for Combinations and Multiset Permutations

Ariel Elboim
preprint en

Abstract

We ask whether all distinct arrangements of a fixed collection of symbols can be visited once by reversing initial segments, with one final reversal returning to the start. Requiring a cycle to contain at least three distinct arrangements, such a listing exists exactly when at least three distinct symbols occur, or when two occur and each occurs at least twice. For binary words, we construct smaller paths with entrance and exit choices that allow them to be joined. For general multisets, we carry colours through binary tours and join the resulting cycles. For the canonical binary cycle, we compute the successor from the current word in linear time. We also stream the reversal lengths with constant worst-case control delay after linear initialization. Both algorithms use linear working space. Control delay measures the work to choose and emit the next reversal length, excluding physical reversal, copying and printing of the word.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon