ในปัญหาการเขียนโปรแกรมนี้ เราได้รับสตริงและเราต้องพิมพ์การเรียงสับเปลี่ยนที่แตกต่างกันขององค์ประกอบสตริงที่สามารถสร้างขึ้นได้ เงื่อนไขของปัญหานี้คือสตริงอาจมีอักขระที่จะเกิดขึ้นมากกว่าหนึ่งครั้ง นอกจากนี้ สตริงที่กำหนดจะถูกป้อนตามลำดับการจัดเรียง
มาดูตัวอย่างเพื่อทำความเข้าใจแนวคิดกันดีกว่า
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.
การเรียงสับเปลี่ยน กำลังจัดเรียงองค์ประกอบทั้งหมดของชุดใหม่ตามลำดับหรือประเภทที่เฉพาะเจาะจง จะสั่งชุดหรือไม่สั่งก็ได้
ตอนนี้เราได้เรียนรู้ทุกอย่างเกี่ยวกับปัญหาแล้ว มาลองสร้างตรรกะในการแก้ปัญหากันเถอะ
เรารู้สูตรทางคณิตศาสตร์ที่เกี่ยวข้องกับพีชคณิต จำนวนสตริงทั้งหมดที่สร้างโดยสตริงที่มีอักขระ n ตัวและทุกอักขระไม่ซ้ำกันถูกกำหนดโดย n! หากมีอักขระในสตริงที่ซ้ำกัน จำนวนสตริงจะได้รับโดย n! / i! .
สำหรับสตริง STURS จำนวนสตริงที่สามารถสร้างได้ทั้งหมดคือ 5! / 2! =60. เนื่องจาก s เกิดขึ้น 2 ครั้งในสตริง
การใช้สิ่งนี้ทำให้เราทราบจำนวนสตริงที่สร้างขึ้น ตอนนี้ เราต้องสร้างสตริงเหล่านั้น สำหรับสิ่งนี้ก่อนอื่น เราจะทำการเรียงลำดับสตริง หากไม่เป็นเช่นนั้น (สตริงที่ป้อนจะถูกจัดเรียง) เพื่อให้สตริงสุดท้ายอยู่ในรูปแบบการเรียงลำดับ ตอนนี้ ให้แก้ไขอักขระตัวแรกของสตริงและค้นหาการเรียงสับเปลี่ยนของอักขระที่เหลือทั้งหมดเป็นต้น สิ่งนี้จะทำให้การเรียงสับเปลี่ยนที่จำเป็นทั้งหมดในลักษณะที่เรียงลำดับ
ตัวอย่างเช่น
ป้อนข้อมูล − RST
ตรรกะ −
จากสตริงนี้ทั้งหมด 3! =เรียงสับเปลี่ยนได้ 6 แบบ
มาแก้ไข R และค้นหาพีชคณิตจาก s และ t ซึ่งจะให้ 2 สตริง RST, RTS
การแก้ไข S ในทำนองเดียวกันจะให้ SRT, STR และการแก้ไข T จะให้ TRS, TSR
ดังนั้น สิ่งนี้จะให้ผลลัพธ์เป็น - RST, RTS, SRT, STR, TRS, TSR ซึ่งเรียงตามลำดับ
ตอนนี้ มาสร้างโปรแกรมเพื่อแก้ปัญหานี้กัน
ตัวอย่าง
#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;
} ผลลัพธ์
The string is : AABC The distinct sorted permutations are : AABC AACB ABAC ABCA ACBA ACAB BAAC BACA BCAA CABA CAAB CBAA
