Chương trình xây dựng dãy hợp lệ lớn nhất theo thứ tự từ điển trong Python

Giả sử ta có một số n, ta cần tìm một dãy thỏa mãn các quy tắc sau:

• Số 1 xuất hiện đúng một lần trong dãy.
• Mỗi số từ 2 đến n xuất hiện đúng hai lần trong dãy.
• Với mọi i từ 2 đến n, khoảng cách giữa hai lần xuất hiện của i chính xác là i.

Khoảng cách giữa hai số trên dãy, a[i] và a[j], là |j - i|. Ta cần tìm dãy lớn nhất theo thứ tự từ điển.

Ví dụ, nếu đầu vào là n = 4, thì đầu ra sẽ là [4, 2, 3, 2, 4, 3, 1].

Giải pháp

Để giải quyết bài toán này, ta thực hiện các bước sau:

• Định nghĩa hàm backtrack(). Hàm này nhận elems, res, start := 0
• Nếu kích thước elems <= 0, trả về True
• Nếu start >= kích thước res, trả về False
• Nếu res[start] khác -1, trả về backtrack(elems, res, start + 1)
• Với i từ 0 đến kích thước elems - 1:
  • num := elems[i]
  • dist := 0 nếu num bằng 1, ngược lại là num
  • Nếu (start + dist) < kích thước res và res[start + dist] bằng -1:
    • res[start] := num
    • res[start + dist] := num
    • Xóa phần tử thứ i khỏi elems
    • Nếu backtrack(elems, res, start) là False:
      • res[start] := -1
      • res[start + dist] := -1
      • Chèn num vào elems tại vị trí i
      • Tiếp tục vòng lặp tiếp theo
    • Ngược lại, trả về True
• Từ phương thức chính:
  • elems := danh sách n phần tử từ n xuống 1
  • res := danh sách kích thước n*2-1 điền bằng -1
  • Gọi backtrack(elems, res)
  • Trả về res

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def backtrack(elems, res, start = 0):
    if len(elems) <= 0:
        return True
    if start >= len(res):
        return False
    if res[start] != -1:
        return backtrack(elems, res, start + 1)
    for i in range(len(elems)):
        num = elems[i]
        dist = 0 if num == 1 else num
        if (start + dist) < len(res) and res[start + dist] == -1:
            res[start] = num
            res[start + dist] = num
            elems.pop(i)
            if not backtrack(elems, res, start):
                res[start] = -1
                res[start + dist] = -1
                elems.insert(i, num)
                continue
            else:
                return True

def solve(n):
    elems = [i for i in range(n,0,-1)]
    res = [-1 for i in range(n*2 - 1)]
    backtrack(elems, res)
    return res

n = 4
print(solve(n))

Đầu vào

4

Đầu ra

[4, 2, 3, 2, 4, 3, 1]