Chương trình đếm hoán vị thỏa điều kiện derangement và chu trình độ k trong Python

Cho n, k. Đếm hoán vị của [1..n] thỏa: (1) không điểm cố định (derangement), (2) tồn tại chu trình độ k.

Thuật toán

• Sinh tất cả hoán vị (chỉ dùng cho n nhỏ).
• Kiểm tra derangement: ∀i, p[i]≠i.
• Kiểm tra có chu trình độ k: duyệt từng đỉnh, theo chu trình đếm độ dài.

Ví dụ

import itertools

def solve(n, k):
    count = 0
    for p in itertools.permutations(range(n)):
        if any(p[i] == i for i in range(n)):
            continue
        for j in range(n):
            cur = p[j]
            length = 1
            while cur != j:
                cur = p[cur]
                length += 1
            if length == k:
                count += 1
                break
    return count

print(solve(3, 2))  # Output: 0

Giải thích

n=3,k=2: derangement là [1,2,0] và [2,0,1] (0-based). Không chu trình độ 2 → 0.