全排列

缘起

请打印出 1~9 所有的全排列

分析

就是dfs. 

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
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
// #define LOCAL
using namespace std;

const int MAX_N = 105;

bool book[MAX_N];
int a[MAX_N], n = 9, cnt; // n表示我们要打印 [1,..,n]的全排列, cnt表示全排列的个数

void dfs(int step) // 现在决定a[step]是什么
{
	if (step == n+1)
	{
		printf("第%d个全排列: ", ++cnt);
		for (int i = 1; i<=n;i++)printf("%d ",a[i]);
		puts("");
		return;
	}
	for (int i = 1; i<=n;i++)
	{
		if (!book[i])
		{
			book[i] = true; // 锁定
			a[step] = i;
			dfs(step+1);
			book[i] = false; // 解锁
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	dfs(1);
	return 0;
}
/*
测试数据
5
1 2
1 3
2 3
2 4
3 4
3 5
4 5
*/