Trong bài toán lập trình này, ta được cho một chuỗi và phải in các hoán vị duy nhất đã sắp xếp của các phần tử chuỗi. Điều kiện: chuỗi có thể chứa ký tự xuất hiện nhiều hơn một lần. Chuỗi đầu vào được cho theo thứ tự đã sắp xếp.
Hãy xem ví dụ để hiểu rõ hơn:
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.
HOÁN VỊ (PERMUTATION) là sắp xếp lại tất cả phần tử của một tập hợp theo trình tự hoặc kiểu cụ thể. Tập hợp có thể đã sắp xếp hoặc chưa.
Bây giờ ta đã hiểu bài toán, hãy tạo logic giải quyết:
Ta biết công thức toán học về hoán vị. Tổng số chuỗi sinh ra từ chuỗi n ký tự tất cả khác nhau là n!. Nếu có ký tự lặp lại, số chuỗi = n! / i! (i là số lần lặp của từng ký tự).
Với chuỗi STURS, tổng chuỗi sinh ra = 5! / 2! = 60 (vì 's' xuất hiện 2 lần).
Dùng điều này ta biết số chuỗi. Bây giờ phải sinh ra các chuỗi đó. Trước tiên sắp xếp chuỗi (đầu vào đã sắp xếp) để kết quả theo thứ tự. Cố định ký tự đầu tiên, tìm hoán vị của phần còn lại, cứ thế. Cách này cho tất cả hoán vị theo thứ tự sắp xếp.
Ví dụ:
Đầu vào − RST
Logic −
Từ chuỗi này có 3! = 6 hoán vị.
Cố định R, tìm hoán vị của S, T → 2 chuỗi: RST, RTS.
Cố định S → SRT, STR. Cố định T → TRS, TSR.
Kết quả: RST, RTS, SRT, STR, TRS, TSR (đã sắp xếp).
Hãy tạo chương trình giải quyết:
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<<endl; 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