Python에서 시작에서 목적지로 이동할 사전순으로 가장 작은 문자열을 찾는 프로그램

데카르트 평면에서 (0, 0) 위치에 있다고 가정합니다. 한 단위의 수평(H) 및 수직(V) 이동만 사용하여 지점(x, y)으로 이동하려고 합니다. 목적지에 도달할 수 있는 방법은 여러 가지가 있습니다. 각 방법은 약간의 H 이동과 적은 V 이동으로 구성됩니다. (예를 들어 (0,0) 지점에서 (2,2) 지점으로 이동하려면 HVVH가 가능한 방법 중 하나입니다.) 다른 값 k가 있는 경우 사전식에서 k번째로 작은 방법을 찾아야 합니다. 목적지로 이동합니다.

따라서 입력이 (x, y) =(3, 3) k =3과 같으면 출력은 "HHVVVH"가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• paths() 함수를 정의합니다. x, y
가 걸립니다.
• min(x, y) <0이면
  • 0을 반환
• factorial(x+y)/factorial(x)/factorial(y) 반환
• 기본 방법에서 다음을 수행합니다. -
• res :=새 목록
• (p, q) :=(0, 0)
• (p, q)가 (x, y)와 같지 않은 동안 do
  • n :=경로(x - p - 1, y - q)
  • p + 1 <=x이고 k
  • 해상도 끝에 'H' 삽입
  • p :=p + 1
• 그렇지 않으면
  • k :=k - n
  • 해상도 끝에 'V' 삽입
  • q :=q + 1

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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