從n個不同元素中不重複地取出m（1≤m≤n）個元素在一個圓周上，叫做這n個不同元素的圓排列。如果一個m-圓排列旋轉可以得到另一個m-圓排列，則認為這兩個圓排列相同。
基本介紹
- 中文名：圓排列
- 範圍：數據結構的一種
定義,計算公式,生成算法,算法證明,舉例,遞歸實現,
定義
從n個不同元素中不重複地取出m（1≤m≤n）個元素在一個圓周上，叫做這n個不同元素的圓排列。如果一個m-圓排列旋轉可以得到另一個m-圓排列，則認為這兩個圓排列相同。
計算公式
n個不同元素的m-圓排列個數N為：
特別地，當m=n時，n個不同元素作成的圓排列總數N為：
生成算法
現在已經存在很多種全排列算法，例如字典序算法、遞增進位制算法、遞減進位制算法、鄰位對換法。這裡介紹一下圓排列生成的算法。我們不妨用1、2、...、n來表示n個元素
對於
，圓排列僅有一種。
對於
，假設我們已經得到了n-1時的圓排列，我們由此序列來生成n的圓排列。
假設
為n-1時的其中一個圓排列，那么我們可以將n分別插入到
後，由此生成新的n-1種排列
......
對
個圓排列均進行此操作，即可生成一組新的一組排列，此排列即為n時的圓排列。
算法證明
首先我們由上述算法能夠得到，對於n，我們生成的排列有
中排列。與圓排列的個數相等，下面我們只需要證明這 個排列無重複即可。首先我們由上述構造方法可知，
一定為每個圓排列的頭。
下用數學歸納法證明：
1. 對於n=1，2，3時，無重複成立。
2. 假設對於n-1時，無重複成立。
3. 對於n時：
由構造方式可知，n是採取插入的方式，故由 生成的n-1個序列中，n左右的兩個元素均不相同。故生成的n-1個序列兩兩不同。
下證由不同圓排列生成的序列無重複。因為 一定為每個圓排列的頭，所以若兩個序列重複，它們一定是完全相同的序列。(例如123 231 312為同一組圓排列，但是由於1一定為頭，所以不可能出現後兩種情況)
假設序列
與序列
重複，由上述可知：
我們去除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 <algorithm>#include <stdio.h>#include <cstdio>#include <cstring>#define MAX_NUM 32using namespace std;typedef uint32_t T;T p[MAX_NUM];int n;void init_p() { for (int i = 0; i < n; i++) p[i] = i + 1;}inline void swap_circle(int i, int j) { T tmp = p[i]; p[i] = p[j]; p[j] = tmp;}/*輸出*/inline void output(int start) { for(int i = 0 ; i < n ; i += 1) { printf("%d", p[(start + i) % n]); if(i != n-1) printf(" "); } printf("\n");}/* 圓排列生成 */void generate_circle(int len) { if (n <= 2) { output(0); return; } if (len == n) { T tmp[MAX_NUM]; memcpy(tmp, p, n * sizeof(T)); for (int i = 1; i < n; ++i) { output_circle(); swap_circle(n-i,n-i-1); } memcpy(p, tmp, n * sizeof(T)); return; } else { T tmp[MAX_NUM]; memcpy(tmp, p, n * sizeof(T)); for (int i = 0; i < len - 1; i++) { generate_circle(len + 1); swap_circle(len - 1 - i, len - 2 - i); } memcpy(p, tmp, n * sizeof(T)); }}int main(int argc, char * argv[]) { scanf("%d", &n); init_p(); //freopen("output.txt", "w",stdout); /*輸出到檔案*/ generate_circle(3); return 0;}