蓝桥杯

文章目录

前言

前面学习了sort排序函数，今天又了解了一下permutations全排列函数。

一、全排列的思路

比如1234这四个数字进行全排列是不是1放在首位234进行全排列，234怎么进行全排列呢是不是2放在首位34进行位置交换，然后2放在首位134进行全排列，以此类推就完成了全排列。
这个时候是不是感受到了递归的思想。

二、permutations函数

函数原型：Perm(char str[], int begin, int end)
str 为需要全排列的数组，begin代表数组首地址，end代表这次全排列过程中，数组的最大索引，也就是这个数组的长度-1，比如abc，第一次递归时， 首地址 0 ，最大索引end为2。
直接看代码：

#include<bits/stdc++.h>  //万能头文件
using namespace std;
void Perm(char str[], int begin, int end) 
{
    int i;
    if (begin == end)   #递归出口
	{
        for (i = 0; i <= end; ++i)
            cout << str[i];
        cout << endl;
    } 
	else
	 {
        for (i = begin; i <= end; ++i) 
		{
            swap(str[i], str[begin]);
            Perm(str, begin+1, end);
            /*
			递归调用，只有第一个变，可以理解成先把a放在开头，把bc全排列，bc全排列的时候又要把b放在bc的开头，把c全排列，以此类推。
			*/
            swap(str[i], str[begin]);
        }
    }
}
int main() 
{
    char str[10];
    cin>>str;
    Perm(str, 0, strlen(str)-1);  //这里长度就strlen函数代替
    return 0;
}

当函数最后begin = end时，无法进行全排列了，只剩下一个字符，输出数组。递归结束。

三、next_permutation

通过不断地搜索的学习，我发现了更简单的实现方法。

#include<bits/stdc++.h>
using namespace std;
int main(){
	char a[10];
    cin >> a;
	do{
		for(int i=0;i<strlen(a);i++)
			cout<<a[i];
		cout<<endl;		
	}while(next_permutation(a,a+strlen(a)));
	return 0;
}