The Library
On a combinatorial generation problem of Knuth
Tools
Merino, Arturo, Micka, Ondrej and Mutze, Torsten (2021) On a combinatorial generation problem of Knuth. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Virtual Conference, 10-13 Jan 2021. Published in: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 735-743. ISBN 9781611976465. doi:10.1137/1.9781611976465.46
|
PDF
WRAP-On-a-combinatorial-generation-problem-Knuth-Mutze-2020.pdf - Accepted Version - Requires a PDF viewer. Download (3296Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611976465.46
Abstract
The well-known middle levels conjecture asserts that for every integer $n\geq 1$, all binary strings of length $2(n+1)$ with exactly $n+1$ many 0s and 1s can be ordered cyclically so that any two consecutive strings differ in swapping the first bit with a complementary bit at some later position.
In his book `The Art of Computer Programming Vol.~4A' Knuth raised a stronger form of this conjecture (Problem~56 in Section~7.2.1.3), which requires that the sequence of positions with which the first bit is swapped in each step of such an ordering has $2n+1$ blocks of the same length, and each block is obtained by adding $s=1$ (modulo $2n+1$) to the previous block.
In this work, we prove Knuth's conjecture in a more general form, allowing for arbitrary shifts $s\geq 1$ that are coprime to~$2n+1$.
We also present an algorithm to compute this ordering, generating each new bitstring in $\mathcal{O}(n)$ time, using $\mathcal{O}(n)$ memory in total.
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Computer programming, Algorithms, Combinatorial analysis | ||||||||||||
Journal or Publication Title: | Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) | ||||||||||||
Publisher: | SIAM | ||||||||||||
ISBN: | 9781611976465 | ||||||||||||
Official Date: | 2021 | ||||||||||||
Dates: |
|
||||||||||||
Page Range: | pp. 735-743 | ||||||||||||
DOI: | 10.1137/1.9781611976465.46 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Re-use Statement: | Copyright © 2021 by SIAM Unauthorized reproduction of this article is prohibited | ||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
Date of first compliant deposit: | 7 October 2020 | ||||||||||||
Date of first compliant Open Access: | 3 September 2021 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | Virtual Conference | ||||||||||||
Date(s) of Event: | 10-13 Jan 2021 | ||||||||||||
Related URLs: | |||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year