递减进位制数法的中介数是什么？

Question

如题所述

Answer 1

全排列公式：全排列数f(n)=n!(定义0!=1)。

全排列是从从N个元素中取出M个元素，并按照一定的规则将取出元素排序，我们称之为从N个元素中取M个元素的一个排列，当M=N时，即从N个元素中取出N个元素的排列。

以最常见的全排列为例，用 S(A)表示集合 A 的元素个数。用 1、2、3、 4、5、6、7、8、9 组成数字不重复的九位数。

则每一个九位数都是集合 A 的一个元素，集合 A 中共有 9个元素，即 S(A)=9。如果集合 A 可以分为若干个不相交的子集，则 A 的元素等于各子集元素之和。

邻位对换法

递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。

这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。

递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。 这个算法可描述如下：

对1—n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1—n的n个排列。

对1—n-1的每一个奇排列，n从左到右插入n个空档，生成1—n的n个排列。

对[2,n]的每个数字都是如此。