Đếm Derangements (Hoán vị sao cho không phần tử nào ở vị trí gốc) trong C++

Derangement là hoán vị của N số sao cho không số nào xuất hiện ở vị trí ban đầu. Ví dụ một derangement của {1,2,3} là {2,1,3}. Không phần tử nào trong này ở vị trí gốc. Mục tiêu ở đây là đếm các derangement có thể có cho N số.

Chúng ta sẽ làm điều này bằng giải pháp đệ quy. Với các số phần tử sau:

• N=0, không có derangement, trả về 1
• N=1, chỉ một số, trả về 0
• N=2, chỉ có một lần hoán đổi vị trí, {1,2} → {2,1}, trả về 1
• N=3, 2 hoán vị có thể, ví dụ {1,2,3} → {2,3,1}, {3,1,2}, đếm 2
• N=4, 9 hoán vị có thể
• .......................
• N, (N-1) * (hoán vị(N-1) + hoán vị(N-2))

Với tất cả phần tử trong mảng:

• Phần tử tại chỉ số 0 có n-1 vị trí nó có thể lấy.
• Nếu phần tử tại chỉ số i được đặt tại chỉ số 0 thì arr[i] và arr[0] được hoán đổi. Bây giờ còn n-2 phần tử để tính toán.
• Nếu phần tử tại chỉ số i không được đặt tại chỉ số 0 thì với n-1 phần tử có n-2 lựa chọn.

Sơ đồ

Ví dụ

Đầu vào

Arr[] = { 1, 2 }

Đầu ra

Số derangements: 1

Giải thích − Vị trí của 1 và 2 là chỉ số 0 và 1. Vị trí duy nhất chúng có thể lấy là hoán đổi vị trí gốc. {2,1}

Đầu vào

Arr[] = { 1, 2, 3 }

Đầu ra

Số derangements: 2

Giải thích − Vị trí của 1,2,3 là chỉ số 0,1,2.

1 có thể đặt tại chỉ số 1 và 2, 2 có thể đặt tại chỉ số 0 và 3, 3 có thể đặt tại chỉ số 0 và 1.

{2,3,1} và {3,1,2} là 2 derangements.

Phương pháp sử dụng trong chương trình dưới đây

• Số nguyên Num lưu số lượng số hiện có.
• Hàm đệ quy derangements(int N) nhận số lượng số làm đầu vào và trả về số derangements.
• Các câu trả về cho N=0,1,2 xử lý các trường hợp cơ sở mà hoán vị đã được tính là 1, 0 và 1.
• Khi N > 2 thì gọi đệ quy derangements() bằng công thức: (N-1) * (derangements(N-1) + derangements(N-2)).
• Khi backtracking bắt đầu, số lượng được tính và trả về.

Ví dụ mã nguồn

#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 << "Số Derangements: " << derangements(Numbers); 
}

Kết quả

Số Derangements: 44