论文标题
关于诺斯的组合生成问题
On a combinatorial generation problem of Knuth
论文作者
论文摘要
众所周知的中层猜想断言，对于每个整数$ n \ geq 1 $，所有长度为$ 2（n+1）$的二进制字符串，恰好$ n+1 $多数0s和1s可以周期订购，以使任何两个连续的串在以后的位置上以互补的位置在第一个位上划分。在他的书《计算机编程艺术》卷中。 4A'Knuth提出了这种猜想的更强形式（第7章，第2.1.3节中的问题56），这要求在此类订购的每个步骤中换位的位置顺序具有相同长度的$ 2N+1 $块，并且通过添加$ S = 1 $ $ 2 $ 2n+1 $ $ 1 $ 1 $ 1 $ 1 $ $ 2n+1 $。在这项工作中，我们以更通用的形式证明了诺斯的猜想，允许任意班次$ s \ geq 1 $，$ s \ geq 1 $占$ 2N+1 $。我们还提出了一种计算此订购的算法，使用$ \ Mathcal {o}（o}（n）$内存，以$ \ mathcal {o}（n）$ time生成每个新的bitstring。
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 Chapter 7, Section 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.
