在 Python 中查找按字典顺序从开始到目的地移动的最小字符串的程序

假设我们在笛卡尔平面的 (0, 0) 位置。我们只想使用单个单位的移动horizontal(H)和vertical(V)移动到达点 (x, y) 。到达目的地的可能方式不止一种。每种方式都包含少量 H 移动和少量 V 移动。（例如，如果我们想从点 (0,0) 到点 (2,2)，那么 HVVH 是一种可能的方式。）如果我们有另一个值 k，我们必须找到字典序第 k 个最小的方式前往目的地。

因此，如果输入类似于 (x, y) = (3, 3) k = 3，那么输出将是“HHVVVH”

示例

让我们看看以下实现以获得更好的理解 -

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))

输入

(3, 3), 3

HHVVVH