पायथन में शब्दकोशीय क्रम से सबसे बड़ा वैध अनुक्रम बनाने का प्रोग्राम

मान लीजिए हमारे पास एक संख्या 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 लेगा
• यदि elems का आकार <= 0, तो
  • True वापस करें
• यदि start >= res का आकार, तो
  • False वापस करें
• यदि res[start] -1 के समान नहीं है, तो
  • वापस करें backtrack(elems, res, start + 1)
• i को 0 से elems के आकार - 1 तक के लिए, करें
  • num := elems[i]
  • dist := 0 जब num 1 के समान हो अन्यथा num
  • यदि (start + dist) < res का आकार और res[start + dist] -1 के समान है, तो
    • res[start] := num
    • res[start + dist] := num
    • elems से i-वां तत्व हटाएं
    • यदि backtrack(elems, res, start) गलत है, तो
      • res[start] := -1
      • res[start + dist] := -1
      • num को elems में स्थिति i पर डालें
      • अगले पुनरावृत्ति के लिए जाएं
    • अन्यथा,
      • True वापस करें
• मुख्य विधि से, निम्न करें
  • elems := n से 1 तक के तत्वों वाली सूची
  • res := n*2-1 आकार की सूची जिसे -1 से भरा गया हो
  • backtrack(elems, res)
  • res वापस करें

उदाहरण

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

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]