Python程式：查詢滿足給定條件的所有排列中的元素個數

假設我們有一個集合A，其中包含從1到n的所有元素。P(A)表示A中所有元素的排列。我們需要找到滿足給定條件的P(A)中的元素個數。

  • 對於所有i∈[1, n]，A[i]不等於i。
  • 存在一個k個索引的集合{i1, i2, ... ik}，使得對於所有j < k，A[ij] = ij+1，並且A[ik] = i1（迴圈）。

因此，如果輸入是n = 3，k = 2，則輸出為0，因為：

考慮陣列從1開始索引。由於N = 3且K = 2，我們可以找到兩個滿足第一個屬性a[i] ≠ i的A集合，它們是[3,1,2]和[2,3,1]。現在，由於K = 2，我們可以有6個這樣的元素。

[1,2]，[1,3]，[2,3]，[2,1]，[3,1]，[3,2]。現在如果我們考慮第一個元素

P(A) -> [3,1,2]

  • [1,2]，A[1] ≠ 2
  • [1,3]，A[1] = 3 但 A[3] ≠ 1
  • [2,3]，A[2] ≠ 3
  • [2,1]，A[2] = 1 但 A[1] ≠ 2
  • [3,1]，A[3] = 1 但 A[1] ≠ 3
  • [3,2]，A[3] ≠ 2

P(A) -> [2,3,1]

  • [1,2]，A[1] = 2 但 A[2] ≠ 1
  • [1,3]，A[1] ≠ 3
  • [2,3]，A[2] = 3 但 A[3] ≠ 2
  • [2,1]，A[2] ≠ 1
  • [3,1]，A[3] = 1 但 A[1] ≠ 3
  • [3,2]，A[3] ≠ 2

由於A的任何元素都不滿足上述屬性，因此為0。

為了解決這個問題，我們將遵循以下步驟：

  • ps := 元素範圍在[1, n]內的所有陣列排列
  • c := 0
  • 對於ps中的每個p，執行：
    • 對於p中的每個索引i和值a，執行：
      • 如果a等於i，則
        • 退出迴圈
    • 否則，
      • 對於j從0到n-1，執行：
        • current := p[j]
        • cycle_length := 1
        • 當current不等於j時，執行：
          • current := p[current]
          • cycle_length := cycle_length + 1
        • 如果cycle_length等於k，則
          • c := c + 1
          • 退出迴圈
  • 返回c

示例

讓我們看看下面的實現來更好地理解：

import itertools

def solve(n, k):
   ps = itertools.permutations(range(n), n)
   c = 0
   for p in ps:
      for i, a in enumerate(p):
         if a == i:
            break
      else:
         for j in range(n):
            current = p[j]
            cycle_length = 1
            while current != j:
               current = p[current]
               cycle_length += 1
            if cycle_length == k:
               c += 1
               break
   return c

n = 3
k = 2
print(solve(n, k))

輸入

3, 2

輸出

0

更新於：2021年10月25日

225 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告