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

मान लीजिए हम कार्टेशियन तल में (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) के समान नहीं है, तब तक:
  • n := paths(x - p - 1, y - q)
  • यदि p + 1 <= x और k < n, तो
    • res के अंत में 'H' डालें
    • p := p + 1
  • अन्यथा,
    • k := k - n
    • res के अंत में '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