题目描述

今天，桐桐的老师布置了一道数学作业，要求列出所有从数字 1 到数字 n 的连续自然数的排列，要求所产生的任一数字序列中不允许出现重复的数字。因为排列数很多，桐桐害怕写漏了，所以她决定用计算机编程来解决。

输入格式

只有一个整数 n（1 ≤ n ≤ 9）。

输出格式

按字典序输出由 1 至 n 组成的所有不重复的数字序列，每行一个序列，每个数字之间有一个空格。

样例

3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

解题思路

我们设想，我们要给一个数组 x[10] 填数，从 x[1] 开始，填到 x[n]，条件是 x[1] 到 x[n] 是没有重复的数字的。每当填完 n 个数字就是找到了一个排列，就输出。

大的思路就是上面说的这样的，从细节来看其实需要考虑好几个问题。从 x[1] 填数填到 x[n]，这是一个层层深入的问题，但是，到什么时候终止，这要控制好。大家看过电影《盗梦空间》没有，电影里面就是一个梦境套一个梦境的，梦里有梦，梦里再有梦....，但是，总要有一个时候你要控制你从某一层梦境中走出来，否则，人就陷入了困境，永远都出不来了。

第二个问题，就是这些排列要有顺序，是要按照字典序来排列的。

我们画了下面的这张图，这是一棵树。数根是 x[0] ，但是本题我们不用 x[0]，我们从 x[1] 开始用，一直用到 x[n]，每当填按 x[i] ，我们就要下探一层，给 x[i+1] 填数。这个过程，可以是一个递归过程。我们还可以通过打标记来记住某一个数字是否已经被用过，用过了就不能在下层的“梦境”里面重复使用。为了让梦境与梦境之间能够共享数据，这个标记数组应该是全局变量。

当我们试图给第 n+1 层（x[n+1]）填数的时候，说明已经完成了从 x[1] 到 x[n] 的填数，这时候就可以输出了。

完善程序

#include<bits/stdc++.h>
using namespace std;
int x[10],n;
bool used[10];
void dfs(int l) // 给 x[l] 填数 
{
	if( 填空(1) ) // 已经填到第 n+1 层，说明了 x[1] 到 x[n] 都填好了； 
	{
		for(int i=1;i<=n;i++)
			printf("%d ",填空(2));
		printf("\n");
	}
	else
	{
		for(int i=1;填空(3);i++) // 枚举所有可填数字
		{
			if(填空(4)){ // 确保 i 是没有用过的 
				x[l] = i; // 给第 l 层数字填 i
				
				used[i] = 填空(5); // 在进入下一层“梦境”之前给 i 打上标记，下层的“梦境”不能再填 i 
				dfs( 填空(6) ); //通过递归函数进入下一层“梦境”，给 x 数组的下一层填数
				填空(7);
			}
		}
	}
}

int main()
{
	cin>>n;
	
	填空(8);

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}

填空(7):{{ input(7) }}

填空(8):{{ input(8) }}