นับ Derangements (การเรียงสับเปลี่ยนที่ไม่มีตัวไหนอยู่ตำแหน่งเดิม) ใน C++

Derangement คือการเรียงสับเปลี่ยนของ N ตัวเลข ที่ไม่มีตัวไหนอยู่ตำแหน่งเดิม เช่น {1,2,3} มี derangement หนึ่งคือ {2,3,1} เป้าหมายคือนับ derangements ทั้งหมดสำหรับ N ตัวเลข

เราใช้ recursive solution สำหรับจำนวนสมาชิก:

• N=0: ไม่มี derangement คืน 1
• N=1: มีแค่ตัวเดียว คืน 0
• N=2: สลับตำแหน่งได้ 1 แบบ {1,2} → {2,1} คืน 1
• N=3: มี 2 แบบ {2,3,1}, {3,1,2} คืน 2
• N=4: มี 9 แบบ
• ...
• N: (N-1) * (derangement(N-1) + derangement(N-2))

สำหรับทุกสมาชิกในอาเรย์:

• สมาชิก index 0 มี N-1 ตำแหน่งที่ไปได้
• ถ้าสมาชิก index i วางที่ index 0 แล้ว arr[i] กับ arr[0] สลับกัน เหลือ N-2 สมาชิก
• ถ้าสมาชิก index i ไม่ได้วางที่ index 0 สำหรับ N-1 สมาชิก มี N-2 ตัวเลือก

Diagram

อินพุต

Arr[] = {1, 2}

เอาต์พุต

No. of derangements: 1

คำอธิบาย − ตำแหน่ง 1 และ 2 คือ index 0 และ 1 สลับได้แค่ {2,1}

อินพุต

Arr[] = {1, 2, 3}

เอาต์พุต

No. of derangements: 2

คำอธิบาย − {2,3,1} และ {3,1,2} คือ 2 derangements

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• ตัวแปร Num เก็บจำนวนตัวเลข
• ฟังก์ชัน derangements(int N) recursive คืนค่าจำนวน derangements
• Base cases: N=0 คืน 1, N=1 คืน 0, N=2 คืน 1
• N>2 ใช้สูตร (N-1) * (derangements(N-1) + derangements(N-2))
• เมื่อ backtracking เริ่ม นับจำนวนและคืนค่า

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int derangements(int N) {
    if (N == 0) return 1;
    if (N == 1) return 0;
    if (N == 2) return 1;
    return (N - 1) * (derangements(N - 1) + derangements(N - 2));
}

int main() {
    int Numbers = 5;
    cout << "Number of Derangements: " << derangements(Numbers);
    return 0;
}

ผลลัพธ์

Number of Derangements: 44