全排列问题回溯解法

经典全排列问题:给定一个序列,输出其所有的全排列结果.

工具函数

def time_memory(func):@functools.wraps(func)def wrapper(*args, **kwargs):tracemalloc.start()start = time.perf_counter()res = func(*args, **kwargs)duration = (time.perf_counter() - start)*1000current, peak = tracemalloc.get_traced_memory()tracemalloc.stop()print(f"{func.__name__} excution duration: {duration:.3f} ms")print(f"{func.__name__} memory usage: current = {current / 1024:.3f} KB, peak = {peak / 1024:.3f} KB")return resreturn wrapper

具体解法

思路: 给定列表可以按照树结构罗列出所有的排序结果,拓扑图如下:

递归处理列表,每一层便利列表元素,将遍历的元素存储于一个trace的列表中,递归之后将trace列表最后一个元素弹出即可,详细python代码如下:

python代码如下:

@time_memory
def permutation(data: list[int]) -> list[list[int]]:res = []track = []def inner(data, track):if len(data) == len(track):# shallow copyres.append(track[:])returnfor item in data:if item in track:continuetrack.append(item)inner(data, track)track.pop()inner(data, track)return resif __name__ == '__main__':data = [1,2,3]res = permutation(data)print(res)

输出:

permutation excution duration: 0.060 ms
permutation memory usage: current = 1.127 KB, peak = 2.408 KB
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]