一个生成组合的新算法

A new algorithm for generating combinations

文章发现了一个生成集合{1,2,…,n}的所有组合的新算法,不仅其理论是初等的,且算法程序化特别容易。利用集合{1,2,…,n}的组合与n位二进制数之间的一一对应关系,该算法从n位二进制数00…0开始,仅仅使用当前n位二进制数一次一个地生成下一个n位二进制数,直到得到最后n位二进制数11…1时算法终止。算法的结果是一个表,该表包含每一个n位二进制数1次且仅1次。该算法不必保留所有n位二进制数的列表就能够简单地用后面的n位二进制数覆盖当前的n位二进制数,且算法是循环的。

A new algorithm for generating all the combinations of {1,2,…,n} is proposed in this paper,which is simple in procedure and elementary in theory.In light of the one-to-one correspondence of combinations of {1,2,…,n}with n-digit binary numbers,starting with the n-digit binary number of 00…0,this algorithm generates the n-digit binary numbers one by one,until the last n-digit binary number of 11…1 is obtained.The result of the algorithm is a list,containing each of n-digit binary numbers which occur only once.Rather than having to retain a list of all the n-digit binary numbers,the presented algorithm overwrites the current n-digit binary number with succeeding one,and it is cyclical.