Trong bài toán lập trình này, chúng ta được cung cấp một chuỗi và chúng ta phải in ra các hoán vị được sắp xếp riêng biệt của các phần tử chuỗi có thể được tạo thành. Điều kiện với vấn đề này là chuỗi có thể chứa một ký tự sẽ phát sinh nhiều hơn một lần. Ngoài ra, chuỗi đã cho được nhập theo thứ tự đã sắp xếp.
Hãy lấy một ví dụ để hiểu rõ hơn về khái niệm này,
Input : ABD Output : ABD , ADB , BAD , BDA , DAB , DBA INPUT : RSTU OUTPUT : RSTU , RSUT , RTSU , RTUS , RUST , RUTS , SRTU , SRUT , STRU , STUR , SURT , SUTR , TRSU , TRUS , TSRU , TSUR , TURS , TUSR , URST , URTS , USRT , USTR , UTRS , UTSR.
GIẤY PHÉP là sắp xếp lại tất cả các phần tử của một tập hợp dựa trên một trình tự hoặc kiểu cụ thể. Bộ có thể được đặt hàng hoặc có thể không được đặt hàng.
Bây giờ khi chúng ta đã tìm hiểu mọi thứ về vấn đề. Hãy cố gắng tạo ra một lôgic để giải quyết vấn đề,
Chúng tôi biết một số công thức toán học liên quan đến hoán vị. Tổng số chuỗi được tạo bởi một chuỗi chứa n ký tự và tất cả các chuỗi đều khác biệt được cho bởi n !. Nếu có các ký tự trong chuỗi đang lặp lại chính nó thì số chuỗi được cho bởi n! / i! .
Đối với chuỗi STURS, tổng số chuỗi có thể được tạo là 5! / 2! =60. Vì s xuất hiện 2 lần trong chuỗi.
Sử dụng điều này, chúng tôi biết số lượng chuỗi được tạo. Bây giờ, chúng ta phải tạo các chuỗi đó. Đối với điều này đầu tiên, chúng tôi sẽ sắp xếp chuỗi nếu không (chuỗi được nhập vào sẽ được sắp xếp) để chuỗi cuối cùng sẽ ở dạng được sắp xếp. Bây giờ, hãy sửa ký tự đầu tiên của chuỗi và tìm hoán vị của tất cả các phần còn lại, v.v. Điều này sẽ cung cấp tất cả các hoán vị bắt buộc theo cách được sắp xếp.
Ví dụ:
Đầu vào - RST
Logic -
Từ chuỗi này tổng 3! =6 hoán vị có thể được tạo thành.
Hãy sửa R và tìm các hoán vị từ s và t. Điều này sẽ cung cấp 2 chuỗi RST, RTS.
Tương tự, việc sửa S sẽ cho ra SRT, STR. Và việc sửa T sẽ tạo ra TRS, TSR.
Vì vậy, điều này sẽ cung cấp đầu ra là - RST, RTS, SRT, STR, TRS, TSR. được sắp xếp theo thứ tự.
Bây giờ, hãy tạo một chương trình để giải quyết vấn đề này,
Ví dụ
#include <bits/stdc++.h>
using namespace std;
bool swaper(char str[], int start, int curr){
for (int i = start; i < curr; i++)
if (str[i] == str[curr])
return 0;
return 1;
}
void printPermutations(char str[], int index, int n){
if (index >= n) {
cout<<str<<"\t";
return;
}
for (int i = index; i < n; i++) {
bool check = swaper(str, index, i);
if (check) {
swap(str[index], str[i]);
printPermutations(str, index + 1, n);
swap(str[index], str[i]);
}
}
}
int main(){
char str[] = "AABC";
int n = strlen(str);
cout<<"The string is : "<<str<<end;
cout<<"The distinct sorted permutations are : \t";
printPermutations(str, 0, n);
return 0;
} Đầu ra
The string is : AABC The distinct sorted permutations are : AABC AACB ABAC ABCA ACBA ACAB BAAC BACA BCAA CABA CAAB CBAA