The coolest way to generate combinations
The coolest way to generate combinations
复制标题
生成组合的最酷方法
DOI：
10.1016/j.disc.2007.11.048
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Williams
中科院分区：
文献类型：
--
作者：
F. Ruskey;A. Williams
我们提出了一种实用而优雅的方法来生成所有 (s,t) 组合（带有 s 个零和 t 个个的二进制字符串）：识别以 010 或 011 结尾的最短前缀（如果不存在这样的前缀，则识别整个字符串），并将其向右旋转一个位置。此迭代规则给出了循环和 genlex 的 (s,t) 组合的顺序。此外，字符串的旋转部分始终包含最多四个连续的零和一，因此每次迭代都可以通过调换最多两对位来实现。这导致了一种高效的无循环和无分支实现，仅包含两个变量和六个赋值语句。该顺序与 colex 顺序也有许多惊人的相似之处，特别是其递归定义和排序算法。鉴于这些相似之处，我们将我们的订单命名为cool-lex！
We present a practical and elegant method for generating all (s,t)-combinations (binary strings with s zeros and t ones): Identify the shortest prefix ending in 010 or 011 (or the entire string if no such prefix exists), and rotate it by one position to the right. This iterative rule gives an order to (s,t)-combinations that is circular and genlex. Moreover, the rotated portion of the string always contains at most four contiguous runs of zeros and ones, so every iteration can be achieved by transposing at most two pairs of bits. This leads to an efficient loopless and branchless implementation that consists only of two variables and six assignment statements. The order also has a number of striking similarities to colex order, especially its recursive definition and ranking algorithm. In the light of these similarities we have named our order cool-lex!