描述項鍊排序的計算方法
基本介紹
- 中文名：項鍊排列
- 定義：描述項鍊排序的計算方法
- 屬性：組合數學中一個很常見的問題
- 特徵：可以在圓排列的基礎上求解
項鍊排列生成算法,算法正確性證明,C/C++遞歸實現,
項鍊排序是組合數學中一個很常見的問題，可以在圓排列的基礎上求解。
·圓周排列：從n箇中取r個的圓排列的排列數為 P(n,r)/r , 2≤r≤n
·項鍊排列：正面向上和反面向上兩種方式放置各個數是同一個排列。因此，從n箇中取r個的項鍊排序數為
P(n,r)/2r, 3≤r≤n
項鍊排列生成算法
現在已經存在很多種全排列算法，例如字典序算法、遞增進位制算法、遞減進位制算法、鄰位對換法。這裡介紹一下項鍊排列生成的算法。我們不妨用1、2、...、n來表示n個元素
對於
，項鍊排列僅有一種。
對於
，假設我們已經得到了n-1時的項鍊排列，我們由此序列來生成n的項鍊排列。
假設
為n-1時的其中一個項鍊排列，那么我們可以將n分別插入到
後，由此生成新的n-1種排列
......
對
個項鍊排列均進行此操作，即可生成一組新的一組排列，此排列即為n時的項鍊排列。
此算法與圓排列算法一致，只不過圓排列從n=3開始插值，而項鍊排列從n=4時插值。
算法正確性證明
首先我們由上述算法能夠得到，對於n，我們生成的排列有
中排列。與項鍊排列的個數相等，下面我們只需要證明這
個排列無重複即可。首先我們由上述構造方法可知，
一定為每個圓排列的頭。
下用數學歸納法證明：
1. 對於n=1，2，3，4時，無重複成立。
2. 假設對於n-1時，無重複成立。
3. 對於n時：
由構造方式可知，n是採取插入的方式，故由 生成的n-1個序列中，n左右的兩個元素均不相同。故生成的n-1個序列兩兩不同。
下證由不同項鍊排列生成的序列無重複。因為 一定為每個項鍊排列的頭，所以若兩個序列重複，它們要么是完全相同的序列, 要么為
與
這樣的形式。(1234 1432為同一組項鍊排列)。但是，由於我們生成算法中不會改變
的相對位置，(例如，將4插入序列123中，123的相對位置不變)，故不可能出現以上情況。
故若序列
與序列
重複，兩者序列一定完全相同。那么去除n後，得到n-1的項鍊排列完全相同，這與假設矛盾，故對於n時生成的算法無重複。
即證。
C/C++遞歸實現
#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(int len) { if (n <= 3) { 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(4); return 0;}