圆排列

定义

计算公式

n个不同元素的m-圆排列个数N为：

特别地，当m=n时，n个不同元素作成的圆排列总数N为：

生成算法

现在已经存在很多种全排列算法，例如字典序算法、递增进位制算法、递减进位制算法、邻位对换法。这里介绍一下圆排列生成的算法。我们不妨用1、2、...、n来表示n个元素

对于

对于

假设

......

对

算法证明

首先我们由上述算法能够得到，对于n，我们生成的排列有

下用数学归纳法证明：

1. 对于n=1，2，3时，无重複成立。

2. 假设对于n-1时，无重複成立。

3. 对于n时：

由构造方式可知，n是採取插入的方式，故由

下证由不同圆排列生成的序列无重複。因为

假设序列

我们去除n后得到n-1的圆排列序列，但是对于n-1，无重複序列，故矛盾。即对于n时生成的算法无重複。

即证。

举例

把n个有标号的珠子排成一个圆圈，共有多少种不同的排法？

解：这是典型的圆排列问题。对于围成圆圈的n个元素，同时按同一方向旋转，即每个元素都向左(或向右)转动一个位置，虽然元素的绝对位置发生了变化，但相对位置未变，即元素间的相邻关係未变，这样的圆排列认为是同一种，否则便是不同的圆排列。下面从三种角度推导圆排列数的计算公式。

方法一：

先令n个相异元素任意排成一行(称为线排列)，共有n!种排法，再将其首尾相接围成一圈，当圆转动一个角度时，对应另一个线排列，当每个元素又转回到原先的位置时，相当于n个不同的线排列，故圆排列数为

方法二：

先取出某一个元素k，放于圆上某确定位置，再令余下的n-1个元素作成一个线排列，首尾置于k的两侧构成一个圆排列同样可得到

方法三：

⊙x1x2…xk，⊙x2x3…xkx1,…，⊙xkx1…xk-1都表示同一环状字，所以⊙x1x2…xk=⊙x2x3…xkx1=…=⊙xkx1…xk-1，有n个这样的等式，其排列数为

递归实现

#include#include#include#include#defineMAX_NUM32usingnamespacestd;typedefuint32_tT;Tp[MAX_NUM];intn;voidinit_p(){for(inti=0;i