"""
全排列生成 — 递归交换法
生成 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)