摘要: 组合算法中一类重要的问题是对排列，组合，子集或整数划分等基本组合结构的有效生成。关于这类生成问题，生成算法的效率很重要。一个常用的提高效率的办法是采用相邻元素间差别很小的生成方式。一个经典的例子是二进制Gray 码，它生成所有n 比特二进制数，使得相邻两个数之间只差一个比特位。组合生成问题有比较广泛的应用领域，包括数据压缩，统计计算，图形图像处理，处理器分配，信息存储和提取等。我们研究用一类特殊的操作来生成组合，即前缀移位。组合用0 与1 组成的比特字符串来表示，例如00110 表示从5 个元素中取出第三，四个元素。前缀移位是将字符串的某一前缀向左或右循环移动一位。F. Ruskey 和A. Williams (Generating Combinations by Prefix Shifts,Proc. 11th Annual International Computing and Combinatorics Conference 2005, LNCS 3595,Springer, (2005), 570-576) 给出了一个新的算法使用前缀移位来生成组合。这个算法描述起来非常简单：找到最短的以010 或011 结尾的前缀将其向右循环移动一位（如果没有这样的前缀就将整个字符串向右循环移动一位）。例如，对于从六个元素中选取三个元素的所有组合（共20 个）的生成如下：111000 —〉011100 —〉 101100 —〉110100 —〉011010 —〉101010 —〉010110 —〉001110 —〉100110 —〉110010 —〉011001 —〉101001 —〉010101—〉001101 —〉100101 —〉010011 —〉001011 —〉 000111 —〉100011 —〉110001。上述生成算法有一些很好的性质。例如，相邻的组合只相差一个前缀移位，适合硬件实现；生成规则是循环的，即对最后一个组合和第一个组合之间生成规则同样适用；相邻组合之间只相差一对或两对0 和1 之间的对换；存在一个有效的算法，对每一个组合计算它在生成序列中的位置等等。F. Ruskey 和A. Williams 提出一个未解决的问题，即能否通过只使用三种基本的前缀移位来生成所有组合，这三种前缀移位分别是字符串的前两位互换和整个字符串向左或右循环移动一位。 本文对这个问题给出否定的回答，我们证明了对于由s 个0 和t 个1 构成的所有组合（即从s+t 个元素中取t 个元素的所有组合），只有当s 和t 中至少有一个不大于2 时，才可以由上述三种前缀移位来生成。