In tất cả các hoán vị theo thứ tự đã sắp xếp (từ vựng) trong C ++

Trong bài toán này, chúng ta được cung cấp một chuỗi có độ dài n và chúng ta phải in tất cả các hoán vị của các ký tự của chuỗi theo thứ tự đã sắp xếp.

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

Đầu vào: ‘XYZ’

Đầu ra: XYZ, XZY, YXZ, YZX, ZXY, ZYX.

Ở đây chúng ta phải in tất cả các hoán vị theo thứ tự từ vựng (thứ tự tăng dần theo bảng chữ cái).

Để giải quyết vấn đề này, trước hết ta phải sắp xếp mảng theo thứ tự tăng dần trong bảng chữ cái, mảng đã sắp xếp là phần tử đầu tiên của hoán vị. Và sau đó tạo hoán vị bậc cao hơn tiếp theo của chuỗi.

Đoạn mã dưới đây sẽ giúp bạn giải quyết rõ ràng hơn:

Ví dụ

#include<iostream>
#include<string.h>
using namespace std;
int compare(const void *a, const void * b){
   return ( *(char *)a - *(char *)b );
}
void swap(char* a, char* b) {
   char t = *a;
   *a = *b;
   *b = t;
}
int finduBound(char str[], char first, int l, int h) {
   int ubound = l;
   for (int i = l+1; i <= h; i++)
      if (str[i] > first && str[i] < str[ubound])
   ubound = i;
   return ubound;
}
void generatePermutaion ( char str[] ) {
   int size = strlen(str);
   qsort( str, size, sizeof( str[0] ), compare );
   bool isFinished = false;
   while ( ! isFinished ) {
      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 ubound = finduBound( str, str[i], i + 1, size - 1 );
         swap( &str[i], &str[ubound] );
         qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );
      }
   }
}
int main() {
   char str[] = "NOPQ";
   cout<<"Permutation in Sorted order :\n";
   generatePermutaion(str);
   return 0;
}

Đầu ra

Permutation in Sorted order :
NOPQ NOQP NPOQ NPQO NQOP NQPO
ONPQ ONQP OPNQ OPQN OQNP
OQPN PNOQ PNQO PONQ POQN
PQNO PQON QNOP QNPO QONP
QOPN QPNO QPON