पायथन में डिकोड XORed क्रमपरिवर्तन खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक सरणी enc है। एक सरणी परमिट है जो पहले एन (विषम) सकारात्मक पूर्णांक का क्रमपरिवर्तन है। इस सूची को लंबाई n-1 के सरणी enc में एन्कोड किया जाएगा, जैसे कि enc[i] =perm[i] XOR perm[i+1]। हमें ओरिजिनल ऐरे पर्म ढूंढना है।

इसलिए, यदि इनपुट एनसी =[2,5,6,3] जैसा है, तो आउटपुट [7, 5, 0, 6, 5] होगा, यहाँ [7 एक्सओआर 5 एक्सओआर 0 एक्सओआर 6 एक्सओआर 5] =[ 2, 5, 6, 3]

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

• n :=enc का आकार
• परिणाम:=आकार की एक सरणी (n+1) और 0 से भरें
• x :=0
• 1 से n+1 की श्रेणी में i के लिए, करें
  • x :=x XOR i
• परिणाम[0] :=x
• 1 से n की श्रेणी में i के लिए, 2 से बढ़ाएँ, करें
  • result[0] :=result[0] XOR enc[i]
• 1 से n की श्रेणी में i के लिए, करें
  • result[i] :=result[i-1] XOR enc[i-1]
• वापसी का परिणाम

उदाहरण

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

def solve(enc):
   n = len(enc)
   result = [0] * (n+1)
   x = 0
   for i in range(1, n+2):
      x ^= i
   result[0] = x
   for i in range(1, n+1, 2):
      result[0] ^= enc[i]
   for i in range(1, n+1):
      result[i] = result[i-1] ^ enc[i-1]
   return result

enc = [2,5,6,3]
print(solve(enc))

इनपुट

[2,5,6,3]

आउटपुट

[7, 5, 0, 6, 5]