Name
Abstract | ||
|---|---|---|
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! |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disc.2007.11.048 | Discrete Mathematics |
Keywords | Field | DocType |
prefix shift.,constant-extra-space,gray code order,branchless algorithm,binary strings,prefix shift,prefix rotation,colex,constant extra space,combinations,loopless algorithm,. gray code order,gray code | Similitude,Discrete mathematics,Combinatorics,Recursion (computer science),Ranking,Loopless algorithm,Iterative method,Gray code,Prefix,Mathematics,Recursive definition | Journal |
Volume | Issue | ISSN |
309 | 17 | Discrete Mathematics |
Citations | PageRank | References |
18 | 0.97 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank Ruskey | 1 | 906 | 116.61 |
| Aaron Williams | 2 | 139 | 20.42 |