Generating Combinations by Prefiz Shifts
We present a new Gray code for combinations that is practical and elegant. We represent combinations as bitstrings with s 0s and t ls, and generate theM with a remarkably simple rule: Identify the shortest prefix ending in 010 or 011 (or the entire bitstring if no such prefix exists) and then rotate (shift) it by one position to the right. Since the rotated portion of the string consists of at most four contiguous runs of Os and ls, each successive combination can be generated by transposing only one or two pairs of bits. This leads to a very efficient loopless implementation. The Gray code also has a simple and efficient ranking algorithm that closely resembles that of combinations in colex order. For this reason, we have given a nickname to our order: cool-lex!
Frank Ruskey Aaron Williams
Dept. of Computer Science, University of Victoria
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
570-576
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）