生成所有错位排列的算法

所谓N元错位排列就是指对应于1,2,–,N的N元排列Im(m1,2,—,N),满足Im!m算法的目的是构造出所有这样的错位排列依据的基本思想是回溯法在沿栈向下试探的过程中逐步扩大部分错位排列的规模当发现无法找到下一个部分错位排列的元素时就向上回溯继续试探,当当回溯至栈空间首元素且栈空间首元素stack[0]N1时表明首元素为2,–,N的所有错位排列已全部试探得到错位排列生成完毕退出循环。这里给出算法该算法生成对应于1,2,—,N的所有N元错位排列代码(C)#include vector #include iostream using namespace std; #define N 5 //问题规模生成对应于1,2,---,N的所有N元错位排列 int Search(const vectorbool occupy, int i, int j) { for (; i occupy.size(); i) { if (i 1 ! j occupy[i] false) { return i 1; } } return 0; } int main() { vectorint a(N, 0); vectorbool occupy(N, false); //对于栈中已生成的错位排列中的任意值i,occupy[i-1]true,对于1,2---,N中不在错位排列栈中的任意元素i,occupy[i-1]false bool TF true; //循环过程中回溯至本层为false,前进至本层为true int i 0; //存放错位排列的栈的栈顶指针 int count 0; //统计错位排列数 while (true) { if (TF false i 0 a[i] N) break; int temp; if (TF false) occupy[a[i] - 1] false; if (TF true (temp Search(occupy, 0, i 1)) 0 || TF false (temp Search(occupy, a[i], i 1)) 0) { --i; TF false; continue; } else { a[i] temp; occupy[temp - 1] true; } if (i ! a.size() - 1) { i; TF true; } else { count; cout 第 count 个错位排列: endl; for (const int m : a) { cout m ; } cout endl; for (int j 1; j N; j) { cout j ; } cout endl; cout endl; TF false; } } return 0; }运行结果(N5时)