把 1∼n
这 n
个整数排成一行后随机打乱顺序,输出所有可能的次序。
输入格式
一个整数 n
。
输出格式
按照从小到大的顺序输出所有方案,每行 1
个。
首先,同一行相邻两个数用一个空格隔开。
其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。
数据范围
1≤n≤9
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
def dfs(index, n, used, arr):
if index == n:
for num in arr:
print(num, end=' ')
print()
return
for i in range(1, n + 1):
if not used[i]:
used[i] = True
arr[index] = i
dfs(index + 1, n, used, arr)
used[i] = False
n = int(input())
used = [False] * (n + 1)
arr = [0] * n
dfs(0, n, used, arr)
解题思路:
首先,这是一个深度优先搜索(DFS)的函数。
dfs函数接受四个参数:index表示当前正在处理的数组位置索引,n表示数组的长度,used 是一个布尔型数组用于标记数字是否已经使用过,arr是用于存储当前排列的数组。
当 index = n时,意味着已经完成了一个排列,所以通过一个循环打印出arr中的每个数字。
然后,通过一个循环从 1到 n 。对于每个数字 i ,如果used[i] 为False,表示这个数字还未被使用。
将 used[i]设为 True ,把i放入arr[index] 中,然后递归调用 dfs函数,将index 增加1 继续处理下一个位置。
递归调用结束后,将 used[i] 重新设为 False ,以便在后续的搜索中可以再次使用这个数字。
在主程序中,首先获取用户输入的 n 。
创建一个长度为n + 1的布尔型数组used并初始化为False。
创建一个长度为n 的数组arr 并初始化为特定值。
最后调用dfs 函数从索引0开始进行深度优先搜索。