全排列的字典序法
#include<stdio.h>int*array;intnum;inlinevoidxchg(int&a,int&b){intc=a;a=b;b=c;}//从pos到num的数据进行翻转voidinvert(intpos){intcount=num-pos+1;for(inti=0;i<count/2;i++)xchg(array[pos+i],array[num-i]);}//检查输入中是否有重复数值boolis_valid(intdata,intserial){for(inti=1;i<serial;i++)if(array[i]==data){printf(全排列中不能有数据重复！\n);return0;}return1;}//输出全排列voidprint_permutation(intm){printf(之后第%d个全排列:,m);for(inti=1;i<=num;i++)printf(%d,array[i]);printf(\n);}//字典序全排列的主体voiddictionary(){printf(输入起始的全排列:\n);for(inti=1;i<=num;i++){intdata;scanf(%d,&data);if(is_valid(data,i))array[i]=data;elsereturn;}if(num==1){printf(只有一个数，不需进行排列！\n);return;}intcount;printf(预测之后第几个序列：\n);scanf(%d,&count);//一次循环找下一个全排列for(intm=1;m<=count;m++){intpos1=0;intpos2;//从num-1开始，找到第一个比右边值小的位置for(intj=num-1;j>0;j--)if(array[j]<array[j+1]){pos1=j;break;}if(pos1<1||pos1>num){printf(目前全排列已为%d位数的最后一个全排列！\n\n,num);return;}//从num开始找array[pos1]小的第一个数的位置for(intn=num;n>pos1;n--)if(array[n]>array[pos1]){pos2=n;break;}xchg(array[pos1],array[pos2]);//从pos1+1到num的数进行翻转invert(pos1+1);print_permutation(m);}}voidmain(){printf(输入要进行全排列的位数\n);scanf(%d,&num);array=newint[num+1];while(1)dictionary();}
