全排序,用Python编写
时间: 2023-05-24 14:05:02 浏览: 82
以下是使用Python编写的全排序算法代码:
```python
def permute(nums):
result = []
dfs(nums, [], result)
return result
def dfs(nums, path, result):
if not nums:
result.append(path)
for i in range(len(nums)):
dfs(nums[:i] + nums[i+1:], path + [nums[i]], result)
# 测试结果
print(permute([1, 2, 3])) # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
```
这个算法使用深度优先搜索来生成所有可能的排列。首先定义一个`permute`函数来接受一个数组作为输入,并返回一个包含所有排列的结果数组。然后,定义一个`dfs`辅助函数来实现深度优先搜索。这个函数接受三个参数:
- `nums`:当前可用的数字数组
- `path`:DFS路径(已选中的数字数组)
- `result`:存储所有排列的结果数组
在`dfs`函数中,首先判断是否已经使用完了所有的数字,如果是,则将当前路径(即已选中的数字数组)添加到结果数组中。否则,对于`nums`数组中的每个数字,都递归调用`dfs`函数,并更新`nums`和`path`参数。在递归回溯后,需要将`nums`和`path`还原到之前的状态,以便进行下一个数字的搜索。
阅读全文