在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

以上是 在C ++中以排序(字典顺序)打印所有排列 的全部内容, 来源链接: utcz.com/z/334766.html

回到顶部