Sự sắp xếp là hoán vị của N số sao cho không có số nào xuất hiện ở vị trí ban đầu. Ví dụ, một sự sắp xếp có thể có của {1,2,3} là {2,1,3}. Không có phần tử nào trong cái này ở vị trí ban đầu của nó. Mục tiêu ở đây là đếm số lần sắp xếp có thể xảy ra cho N số.
Chúng tôi sẽ làm điều này bằng cách sử dụng một giải pháp đệ quy. Đối với sau không. trong số các phần tử -
- N =0, không có sự sắp xếp, trả về 1
- N =1, chỉ một số, trả về 0
- N =2, chỉ có thể hoán đổi vị trí một lần, {1,2} → {2,1}, trả về 1
- N =3, 2 hoán vị có thể có, ví dụ:{1,2,3} → {2,3,1}, {3,1,2} đếm 2
- N =4, 9 hoán vị có thể có
- .......................
- N, (N-1) * (hoán vị (N-1) + hoán vị (N-2))
Đối với tất cả các phần tử trong một mảng,
-
Phần tử ở chỉ mục 0 có n-1 vị trí mà nó có thể đảm nhận,
-
Nếu bất kỳ phần tử nào ở chỉ mục i được đặt ở chỉ mục 0 thì arr [i] và arr [0] được đổi chỗ cho nhau. Bây giờ có n-2 nguyên tố để tính toán.
-
Nếu phần tử ở chỉ mục i không được đặt ở chỉ mục 0 thì đối với n-1 phần tử có n-2 lựa chọn.
Sơ đồ
Đầu vào
Arr[] = { 1, 2 } Đầu ra
No. of derangements : 1
Giải thích - Vị trí 1 và 2 là chỉ số 0 và 1. Chỉ vị trí họ có thể nhận được là hoán đổi vị trí ban đầu. {2,1}
Đầu vào
Arr[] = { 1, 2, 3 } Đầu ra
No. of derangements : 2
Giải thích - Vị trí 1,2 và 3 là chỉ số 0,1,2.
1 có thể được đặt ở chỉ số 1 và 2, 2 có thể được đặt ở chỉ số 0 và 3 và 3 có thể được đặt ở chỉ số 0 và 1.
{2,3,1} và {3,1,2} là 2 biến vị.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Số nguyên lưu trữ số lượng các số hiện có.
-
Hàm đệ quy derangements (int N) lấy số đếm làm đầu vào và trả về số không. của sự thay đổi.
-
Các câu lệnh trả về cho N =0,1,2 đang xử lý các trường hợp cơ sở mà các hoán vị đã được tính là 1,0 và 1.
-
Khi N> 2 thì lệnh gọi đệ quy tới derangements () được thực hiện bằng công thức,
(N-1) * (derangements (N-1) + derangements (N-2)).
Khi bắt đầu theo dõi ngược, số lượng sẽ được tính toán và trả về.
Ví dụ
#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);
} Đầu ra
Number of Derangements :44