Combinatorial Analysis and Computers
Combinatorial Analysis and Computers
复制标题
组合分析和计算机
DOI：
10.1080/00029890.1965.11970695
复制
发表时间：
1965
期刊：
影响因子：
--
通讯作者：
D. Knuth
中科院分区：
文献类型：
--
作者：
M. Hall;D. Knuth
1.引言。计算机的“逻辑决策”特性使它们能够解决许多基本上不是数字的问题。组合构造和搜索就是这类应用，在这种应用中，计算机已经非常成功。计算机在这些问题中使用的两种主要方式是：1)作为较大问题的一部分生成组合模式序列；2)手工计算不可行的构造和搜索。由于组合问题的规模增长非常迅速，我们通常可以预期计算机只能处理比人工所能完成的一个案例。例如，构造n阶有限平面的问题等价于以受限的方式选择(n-1)2则！N个字母的排列；因此，将n改为n+1将使问题大许多个数量级。组合序列。许多计算机应用要求生成组合序列，例如n个元素上的所有排列的集合、一次取n个事物的m个事物的所有组合的集合等等。最简单的组合序列是所有有序n元组(x1，x2，···，x，.)的集合。当然，这个集合可以通过在m进制数系统中重复加1来生成；然而，在应用中，如果以这样的方式生成n元组通常更有用，即每一步[5，7]只改变一个x。最简单的方法如下：在第k步，1k<；m“，加1到x，._，(模m)如果m‘是m除以k的最高幂。当k是m的倍数时，假设(0，0，···，0)是开始的n元组，则不难证明这将是最右边非零数位紧靠左边的数字。在m=2的情况下，产生了所谓的格雷二进制数，它在工程上有许多应用，而该序列是众所周知的解决中国古典环解问题的方法[2]。
1. Introduction. The" logical decision-making" characteristics of computers enable them to attack many problems which are not basically numerical. Combinatorial constructions and searches are applications of this kind in which computers have been very successful. The two principal ways in which computers have been used in these problems are: 1) generation of a sequence of combinatorial patterns as part of a larger problem, and 2) constructions and searches for which hand calculations are unfeasible. Since the size of combinatorial problems grows very rapidly, we can usually expect the computer to do only about one case larger than can be done by hand. For example, the problem of constructing a finite plane of order n is equivalent to choosing, in a restricted way,(n-1) 2 of then! permutations on n letters; thus, changing n to n+ 1 will make the problem many orders of magnitude larger.2. Combinatorial sequences. Many computer applications call for the generation of combinatorial sequences such as the set of all permutations on n elements, the set of all combinations of m things taken n at a time, and so on. The simplest combinatorial sequence is the set of all ordered n-tuples (x1, x2,···, x,.) for which 0~ x,< m, 1~ i~ n. This set can, of course, be gener-: tted by repeatedly adding 1 in the m-ary number system; in applications, however, it is usually more useful if the n-tuples are generated in such a way that only one x, changes at each step [5, 7]. The simplest method for doing this is the following: At the kth step, 1~ k< m", add 1 to x,. _,(modulo m) if m'is the highest power of m dividing k. Whenever k is a multiple of m, it is not difficult to prove that this will be the digit immediately left of the rightmost nonzero digit, assuming (0, 0,···, 0) was the starting n-tuple. The case m= 2 gives rise to the so-called Gray binary numbers which have found many engineering applications, and the sequence is the well-known procedure for solving the classical Chinese Ring Puzzle [2].