在Python中计算相邻对和为完美平方数的排列数量的程序

假设我们有一个名为nums的数字列表。我们必须找到nums的排列数量，每个相邻值的和都是完美平方数。当存在某个索引i使得A[i]不同于B[i]时，两个排列A和B是唯一的。

因此，如果输入为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未被访问过，且(s的平方根) ^ 2 = s，则
  - 将s标记为访问过
  - 交换nums[i+1]和nums[j]
  - util(i+1)
  - 交换nums[i+1]和nums[j]
从主方法中执行以下操作−
visited := 空集
对于i在区间0到nums的大小，做如下操作
- 交换nums[i]和nums[0]
- 如果nums[0]没有被访问过，则
  - util(0)
- 将nums[0]标记为已访问
- 交换nums[i]和nums[0]
返回res

让我们看下面的实现，以便更好地理解−

更多Python相关文章，请阅读：Python 教程

示例

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))