পাইথনে শুরু থেকে গন্তব্যে যাওয়ার জন্য অভিধানের দিক থেকে সবচেয়ে ছোট স্ট্রিং খুঁজে বের করার প্রোগ্রাম

ধরুন আমরা কার্টেসিয়ান সমতলে (0, 0) অবস্থানে আছি। আমরা একক ইউনিটের শুধুমাত্র অনুভূমিক(H) এবং উল্লম্ব(V) চালগুলি ব্যবহার করে বিন্দুতে (x, y) যেতে চাই। গন্তব্যে পৌঁছানোর একাধিক সম্ভাব্য উপায় রয়েছে। প্রতিটি উপায়ে কয়েকটি H চাল এবং কয়েকটি V চাল থাকে। (উদাহরণস্বরূপ যদি আমরা বিন্দু (0,0) থেকে বিন্দুতে (2,2) যেতে চাই, তাহলে HVVH হল সম্ভাব্য উপায়গুলির মধ্যে একটি।) যদি আমাদের আরেকটি মান k থাকে, তাহলে আমাদের অভিধানিকভাবে kth-এর ক্ষুদ্রতম উপায় খুঁজে বের করতে হবে। গন্তব্যে যাচ্ছে।

সুতরাং, যদি ইনপুটটি হয় (x, y) =(3, 3) k =3, তাহলে আউটপুট হবে "HHVVVH"

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন পাথ () সংজ্ঞায়িত করুন। এটি x, y
লাগবে
• যদি min(x, y) <0, তারপর
  • রিটার্ন 0
• ফ্যাক্টোরিয়াল(x+y)/ফ্যাক্টোরিয়াল(x)/ফ্যাক্টোরিয়াল(y)
• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
• res :=একটি নতুন তালিকা
• (p, q) :=(0, 0)
• যখন (p, q) একই নয় (x, y), do
  • 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