이 프로그래밍 문제에서 문자열이 주어지고 구성할 수 있는 문자열 요소의 고유한 정렬된 순열을 인쇄해야 합니다. 이 문제의 조건은 문자열에 두 번 이상 발생할 문자가 포함될 수 있다는 것입니다. 또한 주어진 문자열을 정렬된 순서로 입력합니다.
개념을 더 잘 이해할 수 있도록 예를 들어 보겠습니다.
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