파이썬에서 인접한 쌍의 합이 완전제곱인 순열의 수를 계산하는 프로그램

nums라는 숫자 목록이 있다고 가정합니다. 인접한 값의 모든 쌍의 합이 완전제곱이 되도록 숫자의 순열 수를 찾아야 합니다. A[i]가 B[i]와 같지 않은 인덱스 i가 있는 경우 두 순열 A와 B는 고유합니다.

따라서 입력이 nums =[2, 9, 7]과 같으면 출력은 [2, 7, 9] 및 [9, 7, 2]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 해상도 :=0

• util() 함수를 정의합니다. 이 시간이 걸립니다

• i + 1이 nums의 크기와 같으면

  • 해상도 :=해상도 + 1

  • 반환

• 방문:=새로운 빈 세트

• 범위 i + 1에서 숫자 크기까지의 j에 대해

  • s :=숫자[i] + 숫자[j]

  • s를 방문하지 않고 (s의 제곱근)^2가 s이면

    • 방문으로 표시

    • 숫자[i + 1]와 숫자[j]를 교환합니다.

    • 유틸리티(i + 1)

    • 숫자[i + 1]와 숫자[j]를 교환합니다.

• 주요 방법에서 다음을 수행하십시오 -

• 방문:=새로운 세트

• 범위 0에서 숫자 크기까지의 i에 대해

  • nums[i]와 nums[0] 교환

  • nums[0]을(를) 방문하지 않으면

    • 유틸리티(0)

  • nums[0]을(를) 방문한 것으로 표시

  • nums[i]와 nums[0] 교환

• 반환 해상도

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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]

출력

2