पायथन में आसन्न जोड़ों का योग पूर्ण वर्ग होने वाले क्रमचयों की संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। हमें nums के उन क्रमचयों की संख्या ज्ञात करनी है जहां आसन्न मानों के प्रत्येक जोड़ का योग एक पूर्ण वर्ग है। दो क्रमचय A और B अद्वितीय हैं जब कोई इंडेक्स i ऐसा हो जहां A[i], B[i] के समान नहीं है।

इसलिए, यदि इनपुट nums = [2, 9, 7] जैसा है, तो आउटपुट 2 होगा, क्योंकि हमारे पास [2, 7, 9] और [9, 7, 2] हैं।

हल करने के चरण

res := 0
util() फ़ंक्शन परिभाषित करें। यह i लेगा
- यदि i + 1, nums के आकार के समान है, तो res := res + 1 और लौटें
- visited := एक नया खाली सेट
- j के लिए i + 1 से nums के आकार तक की रेंज में, करें
  - s := nums[i] + nums[j]
  - यदि s, visited में नहीं है और (s का वर्गमूल)^2, s है, तो
    - s को visited के रूप में चिह्नित करें
    - nums[i + 1] और nums[j] को स्वैप करें
    - util(i + 1)
    - nums[i + 1] और nums[j] को स्वैप करें

मुख्य विधि से निम्नलिखित करें:

visited := एक नया सेट
i के लिए 0 से nums के आकार तक की रेंज में, करें
- nums[i] और nums[0] को स्वैप करें
- यदि nums[0], visited में नहीं है, तो util(0)
- nums[0] को visited के रूप में चिह्नित करें
- nums[i] और nums[0] को स्वैप करें
res लौटाएं

उदाहरण

from math import sqrt

class Solution:
    def solve(self, nums):
        self.res = 0
        def util(i):
            if i + 1 == len(nums):
                self.res += 1
                return
            visited = set()
            for j in range(i + 1, len(nums)):
                s = nums[i] + nums[j]
                if s not in visited and int(sqrt(s)) ** 2 == s:
                    visited.add(s)
                    nums[i + 1], nums[j] = nums[j], nums[i + 1]
                    util(i + 1)
                    nums[i + 1], nums[j] = nums[j], nums[i + 1]
        visited = set()
        for i in range(len(nums)):
            nums[i], nums[0] = nums[0], nums[i]
            if nums[0] not in visited:
                util(0)
            visited.add(nums[0])
            nums[i], nums[0] = nums[0], nums[i]
        return self.res

ob = Solution()
nums = [2, 9, 7]
print(ob.solve(nums))

इनपुट

[2, 9, 7]