पायथन में शुरू से गंतव्य तक जाने के लिए लेक्सिकोग्राफिक रूप से सबसे छोटी स्ट्रिंग खोजने का कार्यक्रम

मान लीजिए हम कार्तीय तल में (0, 0) स्थिति पर हैं। हम एकल इकाई के केवल क्षैतिज (H) और ऊर्ध्वाधर (V) चालों का उपयोग करके बिंदु (x, y) पर जाना चाहते हैं। गंतव्य तक पहुंचने के एक से अधिक संभावित तरीके हैं। प्रत्येक मार्ग में कुछ H चालें और कुछ V चालें होती हैं। (उदाहरण के लिए यदि हम बिंदु (0,0) से बिंदु (2,2) पर जाना चाहते हैं, तो HVVH संभावित तरीकों में से एक है। गंतव्य पर जा रहे हैं।

इसलिए, यदि इनपुट (x, y) =(3, 3) k =3 जैसा है, तो आउटपुट "HHVVVH" होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन पथ परिभाषित करें() । इसमें x, y लगेगा
अगर मिनट(x, y) <0, तो
- वापसी 0
रिटर्न फैक्टोरियल(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

शामिल होने के बाद res के वर्ण लौटाएं

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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