C++の入力で許可された重複を含む個別のソートされた順列を出力します

このプログラミングの問題では、文字列が与えられ、形成できる文字列要素の個別にソートされた順列を出力する必要があります。この問題の条件は、文字列に複数回出現する文字が含まれている可能性があることです。また、指定された文字列はソート順に入力されます。

概念をよりよく理解するために例を見てみましょう。

Input : ABD
Output : ABD , ADB , BAD , BDA , DAB , DBA
INPUT : RSTU
OUTPUT : RSTU , RSUT , RTSU , RTUS , RUST , RUTS , SRTU , SRUT , STRU , STUR , SURT , SUTR , TRSU , TRUS , TSRU , TSUR , TURS , TUSR , URST , URTS , USRT , USTR , UTRS , UTSR.

順列 特定のシーケンスまたはタイプに基づいて、セットのすべての要素を再配置しています。セットは注文される場合とされない場合があります。

今、私たちは問題についてすべてを学んだので。問題を解決するためのロジックを作成してみましょう。

順列に関連するいくつかの数式を知っています。 n文字を含み、すべてが異なる文字列によって生成される文字列の総数は、n！で与えられます。文字列内にそれ自体を繰り返している文字がある場合、文字列の数は n！で与えられます。 /私！ 。

文字列STURSの場合、生成できる文字列の総数は5つです。 / 2！ =60。sは文字列内で2回出現するため。

これを使用して、作成された文字列の数がわかります。次に、これらの文字列を作成する必要があります。この最初の場合、そうでない場合は文字列を並べ替えます（入力された文字列は並べ替えられます）。これにより、最終的な文字列が並べ替えられた形式になります。次に、文字列の最初の文字を修正し、残りすべての順列を見つけます。これにより、必要なすべての順列が並べ替えられて表示されます。

たとえば、

入力 − RST

ロジック −

この文字列から合計3つ！ =6つの順列を形成できます。

Rを修正して、sとtから順列を見つけましょう。これにより、2つの文字列 RST、RTSが得られます。

同様に、Sを修正すると、 SRT、STRが得られます。 また、Tを修正すると、 TRS、TSRが得られます。

したがって、これにより、出力は- RST、RTS、SRT、STR、TRS、TSRになります。 並べ替え順です。

それでは、この問題を解決するためのプログラムを作成しましょう。

例

#include <bits/stdc++.h>
using namespace std;
bool swaper(char str[], int start, int curr){
   for (int i = start; i < curr; i++)
      if (str[i] == str[curr])
      return 0;
   return 1;
}
void printPermutations(char str[], int index, int n){
   if (index >= n) {
      cout<<str<<"\t";
      return;
   }
   for (int i = index; i < n; i++) {
      bool check = swaper(str, index, i);
      if (check) {
         swap(str[index], str[i]);
         printPermutations(str, index + 1, n);
         swap(str[index], str[i]);
      }
   }
}
int main(){
   char str[] = "AABC";
   int n = strlen(str);
   cout<<"The string is : "<<str<<end;
   cout<<"The distinct sorted permutations are : \t";
   printPermutations(str, 0, n);
   return 0;
}

The string is : AABC
The distinct sorted permutations are : AABC AACB
   ABAC ABCA ACBA ACAB BAAC
   BACA BCAA CABA CAAB CBAA