全排列

发表于   |   分类于   |  

深度优先搜索

深度优先搜索基本模型

1
2
3
4
5
6
7
8
9
10
11
void DFS(int step)
{
    判断边界
    尝试每一种可能 for(i=0;i<n;i++)
    {
        如果此步可行，则记录此步
        继续下一步，DFS(step+1)
        回溯，取消上一步的记录
    }
    返回
}

例子

用深度优先搜索进行全排列

描述： 输入K个字符，输出其全排列

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<stdio.h>
#include<vector>
#include<string.h>
#include<iostream>
using namespace std;

vector<vector<char> >  result;
vector<bool> mark;
char str[100];

void DFS(char* temp,int n,int len)//temp为输出列表，n为temp中的第几个位置
{
	if(n==len)
	{
		result.push_back(vector<char>(temp,temp+len));//这里需要看一下
	}
	for(int j=0;j<len;j++)//走到一个地方后，要探寻从这个地方可以去其他地方的所有可能
		//这里为：str中的第n个位置该放哪个字符呢？0~len-1全试一遍
	{
		if(mark[j]) continue; //如果第j个字符已经放置过
		temp[n]=str[j];
		mark[j]=true;
		DFS(temp,n+1,len);
		mark[j]=false;
	}
}

void Print()
{
	cout<<"result : "<<result.size()<<endl;
	for(int i=0;i<result.size();i++)
	{
		for(int j=0;j<result[i].size();j++)
		{
			cout<<result[i][j]<<' ';
		}
		cout<<endl;
	}
}

int main()
{
	while(gets(str))
	{
		int len=strlen(str);
		char *temp=new char[len];
		mark.resize(len,false);
		DFS(temp,0,len);
		delete[] temp;
		Print();
	}
	return 0;
}