Pythonで原点から目的地までの移動経路のうち、辞書順でk番目に小さい文字列を求めるプログラム

問題概要

二次元平面上の原点 (0, 0) にいる状態から、1単位ずつの水平移動(H)と垂直移動(V)のみを使って点 (x, y) へ移動することを考えます。目的地への到達方法は複数存在し、それぞれの経路は「H」と「V」の列で表現できます。たとえば、(0, 0) から (2, 2) へ移動する場合、「HVVH」は有効な経路の一つです。

ここで整数 k が与えられたとき、すべての経路を辞書順に並べた際の k 番目の経路(文字列)を求めます。

たとえば、入力が (x, y) = (3, 3)、k = 3 の場合、出力は「HHVVVH」になります。

解法の考え方

この問題は、各ステップで「次に H を選んだ場合に作れる経路の総数」を数えながら、答えとなる文字列を1文字ずつ確定させていく貪欲法で解くことができます。

まず、現在位置 (p, q) から目的地 (x, y) までの総経路数を返す関数 paths() を定義します。残りの移動は H が (x − p) 回、V が (y − q) 回なので、その並べ方の総数は二項係数 C(x + y, x) = (x + y)! / (x! × y!) で求められます。min(x, y) < 0 の場合は経路が存在しないため 0 を返します。

あとは次の手順で経路を構築していきます。

• 結果を格納するリスト res を用意し、現在位置を (p, q) = (0, 0) に初期化します。
• (p, q) が (x, y) と一致するまで、次を繰り返します。
  • n := paths(x − p − 1, y − q) … 次に H を選んだ場合の残りの経路数
  • p + 1 ≤ x かつ k < n ならば、「H」を res の末尾に追加し、p を 1 増やします(先頭が H になる経路は全部で n 個あるため、k がその範囲内なら答えは H で始まります)
  • そうでなければ、k := k − n として「V」を res の末尾に追加し、q を 1 増やします。
• 最後に res を連結した文字列を返します。

実装例

以下に 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))

入力

(3, 3), 3

出力

HHVVVH

補足：より堅牢な実装について

上記のコードでは除算に「/」(浮動小数点除算)を使用しているため、x や y が大きくなると階乗の値が巨大になり、精度の低下が発生する可能性があります。Python 3.8 以降では math.comb(n, r) を使うことで、誤差のない正確な整数演算で二項係数を求められます。

from math import comb

def paths(x, y):
   if min(x, y) < 0:
      return 0
   return comb(x + y, x)

また、solve() 内で毎回 paths() を呼び出す代わりに、必要な二項係数を事前に計算しておく、あるいは動的計画法(DP)で経路数のテーブルを作成しておくことで、大きな入力に対しても高速かつ安定に動作させることができます。