枚举原先相邻的数不相邻的排列的算法

考虑如下问题编号依次为1,2,—n的n个人依照编号次序排成环形,现要将这n个人重新排列成环形,使得在原先的环形排列中彼此相邻的两个人在新的环形排列中不相邻试设计算法枚举满足要求的所有新的环形排列。注意在满足要求的任意一个环形排列中以排列中n个人的每一个人作为起点顺时针或逆时针绕排列一圈 回到作为起点的人所形成的序列对应的都是同一种合法的环形排列因此在枚举过程要求仅保留从n个人中仅一个人出发形成的顺时针(或逆时针)排列,注意是在算法运行过程中剔除多余环形排列,而不是从生成的含有重复结果的排列集合中剔除重复环形排列C代码如下:#includeiostream#includevectorusingnamespacestd;size_t N9;size_tpre_pos(size_t pos){if(pos0)returnN-1;returnpos-1;}size_tnext_pos(size_t pos){if(posN-1)return0;returnpos1;}size_tfind_next_pos(size_t num,vectorsize_tpos_of_Num,vectorsize_tNum_in_pos,size_t cur_pos,size_t count){size_t prepre_pos(cur_pos);size_t nextnext_pos(cur_pos);for(;numN;num){if(pos_of_Num[num]N){size_t adj_num_1pre_pos(num);size_t adj_num_2next_pos(num);if((pos_of_Num[adj_num_1]N||pos_of_Num[adj_num_1]!prepos_of_Num[adj_num_1]!next)(pos_of_Num[adj_num_2]N||pos_of_Num[adj_num_2]!prepos_of_Num[adj_num_2]!next)){if(count!0cur_posN-1Num_in_pos[1]num)returnN;returnnum;}}}returnN;}intmain(){vectorsize_tpos_of_Num(N,N);//各数的位置vectorsize_tNum_in_pos(N,N);//各位置上的数size_t i1;size_t count0;pos_of_Num[0]0;Num_in_pos[0]0;while(true){boolendNum_in_pos[i]N;size_t r;if((rfind_next_pos(end?1:Num_in_pos[i]1,pos_of_Num,Num_in_pos,i,count))N){if(i1)break;if(Num_in_pos[i]!N){pos_of_Num[Num_in_pos[i]]N;Num_in_pos[i]N;}--i;continue;}if(!end)pos_of_Num[Num_in_pos[i]]N;Num_in_pos[i]r;pos_of_Num[r]i;if(i!N-1){i;}else{count;cout第count个解:endl;coutpos:;for(size_t i1;iN;i){couti ;}coutendl;coutnum:;for(size_t i0;iN;i){coutNum_in_pos[i]1 ;}coutendl;coutendl;}}cout共有count个解endl;return0;}