Pythonで開始から宛先に移動する辞書式最小の文字列を見つけるプログラム

デカルト平面の（0、0）の位置にいると仮定します。単一ユニットの水平（H）および垂直（V）移動のみを使用して、ポイント（x、y）に移動します。目的地に到達する方法は複数あります。それぞれの方法は、いくつかのHの動きといくつかのVの動きで構成されます。 （たとえば、ポイント（0,0）からポイント（2,2）に移動する場合、HVVHは可能な方法の1つです。）別の値kがある場合、辞書式順序でk番目に小さい方法を見つける必要があります。目的地に行きます。

したがって、入力が（x、y）=（3、3）k =3の場合、出力は「HHVVVH」になります

これを解決するには、次の手順に従います-

• 関数paths（）を定義します。これにはx、yが必要です
• min（x、y）<0の場合、
  • 0を返す
• 階乗（x + y）/階乗（x）/階乗（y）を返す
• メインの方法から、次の手順を実行します-
• res：=新しいリスト
• （p、q）：=（0、0）
• （p、q）は（x、y）と同じではありませんが、
  • n：=パス（x-p-1、y-q）
  • p + 1 <=xかつk
  • resの最後に「H」を挿入
  • p：=p + 1
• それ以外の場合、
  • k：=k-n
  • resの最後に「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