Generating combinations by three basic operations

作者：Cheng Yongxi^*

来源：Journal of Computer Science and Technology, 2007, 22(6): 909-913.

DOI：10.1007/s11390-007-9094-7

• generating combinations
• gray codes
• prefix shifts

We investigate the problem of listing combinations using a special class of operations, prefix shifts. Combinations are represented as bitstrings of 0's and 1's, and prefix shifts are the operations of rotating some prefix of a bitstring by one position to left or right. We give a negative answer to an open problem asked by F. Ruskey and A. Williams (Generating combinations by prefix shifts, In Proc. 11th Annual International Computing and Combinatorics Conference 2005, LNCS 3595, Springer, 2005, pp.570 similar to 576), that is whether we can generate combinations by only using three very basic prefix shifts on bitstrings, which are transposition of the first two bits and the rotation of the entire bitstring by one position in either direction (i.e., applying the permutations sigma(2), sigma (n) and sigma (-1)(n) to the indices of the bitstrings).

• 出版日期2007-11
• 单位清华大学