生成组合对象的算法（减治法）.docx

组合对象中最重要的类型就是排列、组合和给定集合的子集。作为问题规模的一个函数，组合对象的数量一般来说是呈指数增长的，有时甚至会更快。 生成排列 对于生成{1,…，n}的所有n!个排列的问题，把该问题的规模减一就是要生成所有（n-1）！个排列。假设这个较小的问题已经解决了，我们可以把n插入n-1个元素的每一种排列中的n个可能位置中区，来得到较大规模问题的一个解。按照这种方式生成的所有排列都是独一无二的，这样，我们得到了{1，…，n}的所有排列。 我们既可以从左到右也可以从右到左把n插入前面生成的排列中。从实际情况来看，下面这种做法是有好处的：一开始从右到左把n插入12……（n-1）的位置中，然后