In tất cả các hoán vị riêng biệt của một chuỗi nhất định với các bản sao trong C ++

Trong bài toán này, chúng tôi đưa ra một chuỗi có thể chứa các ký tự trùng lặp. Nhiệm vụ của chúng tôi là in tất cả các hoán vị riêng biệt của các chuỗi.

Hãy lấy một ví dụ để hiểu vấn đề -

Input: string = “XYZ”
Output: XYZ XZY YXZ YZX ZYX ZXY

Để giải quyết vấn đề này, chúng ta phải sửa một phần tử của chuỗi. Và sau đó lặp lại tất cả các phần tử của chuỗi.

Ví dụ

Chương trình triển khai giải pháp của chúng tôi,

#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;
}

Đầu ra

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