Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 중복이 있는 주어진 문자열의 모든 고유한 순열을 인쇄합니다.


이 문제에서는 중복 문자를 포함할 수 있는 문자열이 제공됩니다. 우리의 임무는 문자열의 모든 고유한 순열을 인쇄하는 것입니다.

문제를 이해하기 위해 예를 들어 보겠습니다 -

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