全排列问题

问题描述

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有 'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入 

输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在 1 到 6之间。

输出

输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：

已知 S=s1​s2​...sk​,T=t1​t2​...tk​，则S<T 等价于，存在p(1≤p≤k)，使得 s1​=t1​,s2​=t2​,...,sp−1​=tp−1​,sp​<tp​ 成立。

Sample 1

Inputcopy	Outputcopy
abc	abc acb bac bca cab cba

解题思路 ：我们可以发现规律，求abc的全排列就是求bc或ac或ab的全排列，求bc的全排列就是求b的全排列和c的全排列，我们可以定义一个函数void permutation(int k),表示从第k个位置开始摆放字母；

第一步就是在第k个位置摆放前面没有用过的字母，在选好第k个位置摆放的字母后，将其存在b[k]里 ；

第二步就是在第k+1个位置及之后的位置上摆放字母，我们可以通过再次调用这个函数，执行permutation(k+1)来实现；

 代码如下

#include<bits/stdc++.h>
using namespace std;

char a[500];//输入的字符串 
char b[500];//求出的排列 
int vis[100];//表示vis[i]中第i个字母是否用过 
int n;
void permutation(int k)//从排列的第k个位置开始往后摆放字母 
{
	if(k==n)//表示到达最后一个字母，不能再交换，最终的排列需要输出 
	{
		for(int i=0;i<k;i++) 
		printf("%c",b[i]);
		printf("\n");
	} 
	for(int i=0;i<n;i++)//在第k个位置穷举所有可能的放法 
	{
		if(vis[i]==0)//如果第i个字母没有用过 
		{
			vis[i]=1;//标志被用 
			b[k]=a[i];//选好第k个位置摆放的字母后，将其存在b[k]里 
			permutation(k+1);//下一位置递归调用 
			vis[i]=0;//恢复初始状态，取消第k个位置的放法，便于下一次尝试另一种放法 
		}
		
    }
}
int main(void)
{
	scanf("%s",a);
	n=strlen(a);
	permutation(0);
	return 0;
 } 

//我又写了一个数字全排列

输入一个整数n(1<=n<=9),输出由1~n组成的所有不重复的数字序列，每行一个序列

#include<bits/stdc++.h>
using namespace std;

int a[500];
int vis[100];
int n;
void dfs(int cur)
{
	if(cur==n)
	{
	for(int i=0;i<n;i++)
	printf("%d ",a[i]);
	printf("\n");
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0)
		{
			vis[i]=1;
			a[cur]=i;
			dfs(cur+1);
			vis[i]=0;
		}
		
    }
}
int main(void)
{
	scanf("%d",&n);
	dfs(0); 
	return 0;
 } 

 注意：如果dfs(1)需要将cur=n+1

dfs(0)和dfs(1)出口不一样，一个是n,一个是n-1.