ในปัญหานี้ เราได้รับสตริงที่อาจมีอักขระที่ซ้ำกัน งานของเราคือการพิมพ์การเรียงสับเปลี่ยนที่แตกต่างกันทั้งหมดของสตริง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −
Input: string = “XYZ” Output: XYZ XZY YXZ YZX ZYX ZXY
เพื่อแก้ปัญหานี้ เราต้องแก้ไของค์ประกอบหนึ่งของสตริง แล้ววนซ้ำองค์ประกอบทั้งหมดของสตริง
ตัวอย่าง
โปรแกรมที่จะใช้โซลูชันของเรา
#include <string.h>
#include <iostream>
using namespace std;
int compare(const void* a, const void* b) {
return (*(char*)a - *(char*)b);
}
void swapChar(char* a, char* b) {
char t = *a;
*a = *b;
*b = t;
}
int findCeil(char str[], char first, int l, int h) {
int ceilIndex = l;
for (int i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
void printPermutations(char str[]) {
int size = strlen(str);
qsort(str, size, sizeof(str[0]), compare);
bool isFinished = false;
while (!isFinished) {
static int x = 1;
cout<<str<<"\t";
int i;
for (i = size - 2; i >= 0; --i)
if (str[i] < str[i + 1])
break;
if (i == -1)
isFinished = true;
else {
int ceilIndex = findCeil(str,
str[i], i + 1, size - 1);
swapChar(&str[i], &str[ceilIndex]);
qsort(str + i + 1, size - i - 1,
sizeof(str[0]), compare);
}
}
}
int main() {
char str[] = "SNGY";
cout<<"All permutations of the string"<<str<<" are :\n";
printPermutations(str);
return 0;
} ผลลัพธ์
All permutations of the stringSNGY are − GNSY GNYS GSNY GSYN GYNS GYSN NGSY NGYS NSGY NSYG NYGS NYSG SGNY SGYN SNGY SNYG SYGN SYNG YGNS YGSN YNGS YNSG YSGN YSNG
