算法笔记:全排列(CC++)

    技术2022-07-13  73

    题目描述: 一般把1~n这n个整数按某个顺序摆放的结果称为这n个整数的一个排列,而全排列只这n个整数能形成的所有排列。例如1、2、3这三个整数的全排列为123、132、213、231、312、321。这些是按照字典序从小到大的顺序给出的。

    解题思路: 从递归的角度去考虑,如果把问题描述为“输出1~n这n个整数的全排列”,可以被分为若干个子问题:“输出以1开头的全排列”“输出以2开头的全排列”…“输出以n开头的全排列”。可以设一个数组P,用来存放当前的排列,再设置一个散列数组,hashTable[x],当x已经在P中时设为true. 现在按照顺序往P的第1位到第n位中填入数字,不妨假设当前已经填好了P[1]~P[index-1]中,正准备填入P[index]。我们需要枚举1-n,如果当前枚举的数字x还没有在P[1]-P[index-1]中,那么就把该数字填入。同时将hashTable[x]置为true,然后去处理P的第 index+1位。 当所有的递归完成后,在将hashTable[x]还原为false.

    递归边界:当index达到n+1时,说明P的第1~n位都已经填好,此时可以把P输出,表示生成了一个排列,然后return即可。

    C/C++代码

    #include<cstdio> const int maxn=11; int n,P[maxn],hashTable[maxn]={false}; //当前处理排列的第index号位 void generateP(int index) { if(index==n+1) { for(int i=1;i<=n;i++) { printf("%d",P[i]); } printf("\n"); return; } //枚举1~n,试图将x填入P[index] for(int x=1;x<=n;x++) { if(hashTable[x]==false) { P[index]=x; hashTable[x]=true; generateP(index+1); hashTable[x]=false; } } } int main() { n=3; //输出1~3的全排列 generateP(1); // 从第一个位置开始填充数字 return 0; }

    递归函数讲解:

    //当前处理排列的第index号位 void generateP(int index) { if(index==n+1) { for(int i=1;i<=n;i++) { printf("%d",P[i]); } printf("\n"); return; } //枚举1~n,试图将x填入P[index] //排列第1个位置 此时hashTable[1]=false,hashTable[2]=false和hashTable[3]=false,分别进行循环 for(int x=1;x<=n;x++) { if(hashTable[x]==false) { P[index]=x; //P[1]=1 hashTable[x]=true; //hashTable[1]=true //generateP(index+1); //每个递归调用处都可以看作把原来的for循环内容执行了一次 //排列第2个位置,此时hashTable[2]=false和hashTable[3]=false,先进行 hashTable[2]=false的循环,再进行hashTable[3]=false 的循环 for(int x=1;x<=n;x++) { if(hashTable[x]==false) { P[index]=x; //P[2]=2 hashTable[x]=true; //hashTable[2]=true //generateP(index+1); //排列第三个位置 for(int x=1;x<=n;x++) { if(hashTable[x]==false) { P[index]=x; //P[3]=3 hashTable[x]=true; //hashTable[3]=true //generateP(index+1); //达到递归边界 if(index==n+1) //index=4 { for(int i=1;i<=n;i++) { printf("%d",P[i]); } printf("\n"); //输出123 return; } hashTable[x]=false; //hashTable[3]=false } } hashTable[x]=false; } } hashTable[x]=false; } } }
    Processed: 0.029, SQL: 9