遍历从N个元素中取M个元素可能组合的最佳算法

The Best Algorithm for Searching through All Possible Combinations of M Elements from N Elements

从N个相异元素中取M个元素(M≤N)的可能组合的遍历问题是组合数学中重要的基础性问题.关于该问题的现行算法是建立在对于搜索到的每一个节点的诸元素首先进行排序,然后搜索下一个节点.本文对于该问题给出一个全新的算法.新算法中放弃了对于节点诸元素的排序,实现每进行一次数据交换即搜索到一个新的节点,因而成为解决该问题的最佳算法.使用该算法编辑计算机程序,有编程简短、占用机器内存小的特点.

It is a fundamental problem that how to search through all possible combinations of M elements from N elements for given positive integers M and N with M ≤ N. This problem is called searchingthroughallcombinations problem, or STAC problem briefly. The current algorithm for STAC problem is as follows: one may first permute all elements in every knot that has been found and then search the next knot. In this paper, a new algorithm for STAC problem is presented. In the new algorithm, the permutations of the elements in the knot that has been found are abandoned, and each time the data are exchanged, a new knot is find. For STAC problem, the new algorithm is the best one, according to many advantages for us to write computer program, for example, the program would be simple, the interior store occupied would be small and much computer time can be saved.