Tìm chuỗi ký tự nhỏ nhất theo thứ tự từ điển để di chuyển từ (0,0) đến (x,y) trong Python

Giả sử chúng ta đang ở vị trí (0, 0) trên mặt phẳng Descartes. Chúng ta muốn đi đến điểm (x, y) chỉ sử dụng các bước ngang (H) và dọc (V) mỗi bước một đơn vị. Có nhiều cách để đến đích. Mỗi cách bao gồm một số bước H và một số bước V. (Ví dụ, nếu muốn đi từ (0,0) đến (2,2), thì HVVH là một trong các cách có thể.) Nếu có thêm giá trị k, ta phải tìm cách đi thứ k theo thứ tự từ điển nhỏ nhất.

Ví dụ: với (x, y) = (3, 3) và k = 3, kết quả sẽ là "HHVVVH".

Giải thuật

• Định nghĩa hàm paths(x, y) trả về số lượng đường đi từ (0,0) đến (x,y) chỉ dùng H và V.
• Nếu min(x, y) < 0, trả về 0.
• Trả về tổ hợp: factorial(x+y) / (factorial(x) * factorial(y)).
• Từ hàm chính:
  • Khởi tạo danh sách kết quả res rỗng.
  • Vị trí hiện tại (p, q) = (0, 0).
  • Khi (p, q) khác (x, y):
    • Tính n = paths(x - p - 1, y - q) (số đường đi nếu đi bước H tiếp theo).
    • Nếu p + 1 ≤ x và k < n: thêm 'H' vào res, tăng p lên 1.
    • Ngược lại: k = k - n, thêm 'V' vào res, tăng q lên 1.
  • Trả về chuỗi kết nối các ký tự trong res.

Ví dụ mã Python

from math import factorial

def paths(x, y):
    if min(x, y) < 0:
        return 0
    return factorial(x + y) // (factorial(x) * factorial(y))

def solve(x, y, k):
    res = []
    p, q = 0, 0
    while (p, q) != (x, y):
        n = paths(x - p - 1, y - q)
        if p + 1 <= x and k < n:
            res.append('H')
            p += 1
        else:
            k -= n
            res.append('V')
            q += 1
    return ''.join(res)

(x, y) = (3, 3)
k = 3
print(solve(x, y, k))  # Output: HHVVVH

Đầu vào

(3, 3), 3

Đầu ra

HHVVVH