Mô phỏng thuật toán Sinh hoán vị (quay lui)

Permutations (Backtracking) · Nhóm: Đệ quy

Sinh mọi hoán vị của một tập bằng quay lui: dựng dần mảng cur, mỗi vị trí chọn một phần tử chưa dùng.

Ý tưởng

Duy trì mảng cur đang xây và mảng used đánh dấu phần tử đã lấy.

Tại mỗi bước, duyệt các phần tử chưa dùng: chọn một phần tử, đánh dấu used, đệ quy xuống vị trí kế.

Khi cur đủ độ dài thì ghi nhận một hoán vị, rồi bỏ chọn (backtrack) để thử phần tử khác.

Vì sao đúng

Mỗi lá của cây lựa chọn là một hoán vị khác nhau; đánh dấu used đảm bảo không lặp phần tử, và bỏ chọn khi quay về giúp tái dùng một mảng cur duy nhất cho mọi nhánh.

Mã Python

def permute(nums, cur, used, out):
    if len(cur) == len(nums):   # a full permutation
        out.append(cur[:])      # record a copy
        return
    for i in range(len(nums)):  # try each element
        if used[i]:
            continue            # skip already-picked
        used[i] = True
        cur.append(nums[i])     # pick nums[i]
        permute(nums, cur, used, out)
        cur.pop()               # unpick (backtrack)
        used[i] = False

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.