โปรแกรมนับจำนวนองค์ประกอบใน permutation ทั้งหมด ที่ตรงตามเงื่อนไข ใน Python

กำหนดเซต A มีสมาชิก 1 ถึง n P(A) คือ permutations ทั้งหมดของ A หาจำนวน permutation ที่ตรงเงื่อนไข:

• สำหรับทุก i ใน [1, n], A[i] ≠ i (derangement)
• มีชุด index k ตัว {i1, i2, ... ik} ที่ A[ij] = ij+1 สำหรับ j < k และ A[ik] = i1 (เป็น cycle)

เช่น n=3, k=2 ผลลัพธ์ 0

วิธีแก้ปัญหา

• ps := permutations ทั้งหมดของ [1..n]
• c := 0
• สำหรับแต่ละ p ใน ps
  • ตรวจสอบทุก index i และค่า a ใน p ถ้า a == i: break
  • มิฉะนั้น ลูป j จาก 0 ถึง n-1
    • current := p[j], cycle_length := 1
    • while current != j: current := p[current]; cycle_length += 1
    • ถ้า cycle_length == k: c += 1; break
• คืนค่า 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))

Input

3, 2

Output

0