Pythonで指定された条件に従っているすべての順列の要素の数を見つけるプログラム

1からnまでのすべての要素が存在する集合Aがあるとします。そして、P（A）はAに存在する要素のすべての順列を表します。与えられた条件を満たすP（A）の要素の数を見つける必要があります

• 範囲[1、n]のすべてのiについて、A[i]はiと同じではありません
• すべてのj

したがって、入力がn =3 k =2の場合、-

配列のインデックスが1であると考えてください。 N=3およびK=2であるため、最初のプロパティa [i]≠iを満たす2セットの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]≠3
• [2,1]、A[2]≠1
• [3,1]、A[3]=ただしA[1]≠3
• [3,2]、A[3]≠2

の要素はいずれも上記のプロパティを満たさないため、0になります。

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

• ps：=範囲[1、n]の要素を持つ配列のすべての順列
• c：=0
• psの各pについて、
  • 各インデックスiおよびpの値aについて、実行します
    • aがiと同じ場合、
      • ループから抜け出す
  • それ以外の場合、
    • 0からn-1の範囲のjの場合、do
      • 現在：=p [j]
      • cycle_length：=1
      • 電流はjと同じではありませんが、
        • current：=p [current]
        • cycle_length：=cycle_length + 1
      • cycle_lengthがkと同じ場合、
        • c：=c + 1
        • ループから抜け出す
• return 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