35 lines
1008 B
Python
35 lines
1008 B
Python
"""
|
|
全排列生成 — 递归交换法
|
|
生成 n 个元素的所有排列 (n!)
|
|
"""
|
|
|
|
def permute(arr, start, end):
|
|
"""递归生成全排列"""
|
|
if start == end:
|
|
print("".join(map(str, arr)))
|
|
else:
|
|
for i in range(start, end + 1):
|
|
arr[start], arr[i] = arr[i], arr[start]
|
|
permute(arr, start + 1, end)
|
|
arr[start], arr[i] = arr[i], arr[start] # 回溯
|
|
|
|
def permute_unique(arr, start, end):
|
|
"""生成去重全排列"""
|
|
if start == end:
|
|
print("".join(map(str, arr)))
|
|
else:
|
|
seen = set()
|
|
for i in range(start, end + 1):
|
|
if arr[i] not in seen:
|
|
seen.add(arr[i])
|
|
arr[start], arr[i] = arr[i], arr[start]
|
|
permute_unique(arr, start + 1, end)
|
|
arr[start], arr[i] = arr[i], arr[start]
|
|
|
|
if __name__ == "__main__":
|
|
print("全排列 [1,2,3]:")
|
|
permute([1, 2, 3], 0, 2)
|
|
|
|
print("\n去重全排列 [1,1,2]:")
|
|
permute_unique([1, 1, 2], 0, 2)
|