Pythonで隣接するペアの合計が完全な二乗である順列の数をカウントするプログラム

numsという番号のリストがあるとします。隣接する値のすべてのペアの合計が完全な二乗になるように、numの順列の数を見つける必要があります。 A[i]がB[i]と同じではないインデックスiがある場合、2つの順列AとBは一意です。

したがって、入力がnums =[2、9、7]の場合、[2、7、9]と[9、7、2]

これを解決するには、次の手順に従います-

• res：=0

• 関数util（）を定義します。これには私がかかります

• i + 1がnumsのサイズと同じである場合、

  • res：=res + 1

  • 戻る

• 訪問した：=新しい空のセット

• i + 1からnumsのサイズまでの範囲のjについては、次のようにします

  • s：=nums [i] + nums [j]

  • sにアクセスせず、（sの平方根）^ 2がsの場合、

    • sを訪問済みとしてマーク

    • nums [i+1]とnums[j]

      を交換します

    • util（i + 1）

    • nums [i+1]とnums[j]

      を交換します

• メインの方法から、次のようにします-

• 訪問した：=新しいセット

• 0からnumsのサイズの範囲のiの場合、実行します

  • nums[i]とnums[0]

    を交換します

  • nums [0]にアクセスしていない場合は、

    • util（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