पायथन में शाब्दिक रूप से सबसे बड़े वैध अनुक्रम के निर्माण का कार्यक्रम

मान लीजिए कि हमारे पास एक संख्या n है, हमें एक ऐसा क्रम खोजना है जो निम्नलिखित सभी नियमों को पूरा करता हो -

• 1 क्रम में एक बार आता है।

• 2 और n के बीच की प्रत्येक संख्या क्रम में दो बार आती है।

• 2 से n तक के प्रत्येक i के लिए, i की दो घटनाओं के बीच की दूरी बिल्कुल i है।

अनुक्रम पर दो संख्याओं के बीच की दूरी, a[i] और a[j], है |j - i|। हमें शब्दावली की दृष्टि से सबसे बड़ा अनुक्रम खोजना है।

इसलिए, यदि इनपुट n =4 जैसा है, तो आउटपुट [4, 2, 3, 2, 4, 3, 1]

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

• एक फ़ंक्शन को परिभाषित करें backtrack() । यह elems लेगा, res, start:=0
• यदि हाथियों का आकार <=0, तो
  • सही लौटें
• यदि प्रारंभ>=रेस का आकार, तो
  • झूठी वापसी
• यदि रेस [प्रारंभ] -1 के समान नहीं है, तो
  • रिटर्न बैकट्रैक(elems, res, start + 1)
• i के लिए 0 से लेकर elems के आकार के लिए - 1, do
  • संख्या:=elems[i]
  • जिला:=0 जब संख्या 1 के समान हो अन्यथा संख्या
  • अगर (स्टार्ट + डिस्ट) <रेस और रेस का आकार [स्टार्ट + डिस्ट] -1 के समान है, तो
    • res[start] :=num
    • res[start + dist] :=num
    • तत्वों से ith तत्व हटाएं
    • यदि बैकट्रैक (एल्स, रेस, स्टार्ट) गलत है, तो
      • res[शुरू] :=-1
      • res[start + dist] :=-1
      • स्थिति i पर Elements में num डालें
      • अगले पुनरावृत्ति के लिए जाएं
    • अन्यथा,
      • सही लौटें
• मुख्य विधि से, निम्न कार्य करें
• elems :=n तत्वों के साथ n से नीचे 1 तक की सूची
• res :=आकार n*2-1 की सूची और -1 से भरें
• बैकट्रैक(एल्स, रेस)
• रिटर्न रेस

उदाहरण

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

def backtrack(elems, res, start = 0):
   if len(elems) <= 0:
      return True

   if start >= len(res):
      return False

   if res[start] != -1:
      return backtrack(elems, res, start + 1)

   for i in range(len(elems)):
      num = elems[i]
      dist = 0 if num == 1 else num

      if (start + dist) < len(res) and res[start + dist] == -1:
         res[start] = num
         res[start + dist] = num
         elems.pop(i)

         if not backtrack(elems, res, start):
            res[start] = -1
            res[start + dist] = -1
            elems.insert(i, num)
            continue
         else:
            return True
def solve(n):
   elems = [ i for i in range(n,0,-1)]
   res = [ -1 for i in range(n*2 - 1)]
   backtrack(elems, res)
   return res

n = 4
print(solve(n))

इनपुट

4

आउटपुट

[4, 2, 3, 2, 4, 3, 1]