พิมพ์พีชคณิตทั้งหมดในการเรียงลำดับ (พจนานุกรม) ใน C ++

ในปัญหานี้ เราได้รับสตริงที่มีความยาว n และเราต้องพิมพ์การเรียงสับเปลี่ยนของอักขระในสตริงตามลำดับการจัดเรียง

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน :

ป้อนข้อมูล: 'XYZ'

ผลลัพธ์: XYZ, XZY, YXZ, YZX, ZXY, ZYX

ที่นี่เราต้องพิมพ์การเรียงสับเปลี่ยนทั้งหมดตามลำดับศัพท์ (ลำดับที่เพิ่มขึ้นตามลำดับตัวอักษร)

เพื่อแก้ปัญหานี้ เราต้องเรียงลำดับอาร์เรย์ในลำดับที่เพิ่มขึ้นตามลำดับตัวอักษรก่อน อาร์เรย์ที่จัดเรียงเป็นองค์ประกอบแรกของการเรียงสับเปลี่ยน แล้วสร้างการเรียงสับเปลี่ยนลำดับที่สูงขึ้นถัดไปของสตริง

โค้ดด้านล่างจะทำให้คุณเห็นวิธีแก้ปัญหาที่ชัดเจนยิ่งขึ้น :

ตัวอย่าง

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

ผลลัพธ์

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