In tất cả các hoán vị có lặp lại các ký tự trong C ++

Trong bài toán này, chúng ta được cung cấp một chuỗi n ký tự và chúng ta phải in ra tất cả các hoán vị của các ký tự của chuỗi. Cho phép lặp lại các ký tự của chuỗi. Việc in hoán vị nên được thực hiện theo thứ tự bảng chữ cái (thứ tự được sắp xếp theo từ vựng).

Hãy lấy một ví dụ để hiểu rõ hơn về chủ đề:

Đầu vào - XY

Đầu ra - XX, XY, YX, YY

Để giải quyết vấn đề này, chúng ta cần sử dụng logic sửa chữa và lặp lại. Ở đây, chúng tôi sẽ sửa một phần tử ở chỉ mục đầu tiên của mảng và sau đó gọi đệ quy cho các phần tử tiếp theo trong chuỗi.

Hãy xem một ví dụ triển khai sẽ làm rõ giải pháp cho bạn.

Nhập chuỗi XY.

Sửa các phần tử đầu tiên ở 1 chỉ mục:X_

Gọi đệ quy các phần tử khác và điền:XX -> XY

Bây giờ, hãy sửa phần tử tiếp theo tại index1:Y_

Gọi đệ quy các phần tử khác và điền:YX-> YY

Logic tương tự có thể được sử dụng cho chuỗi độ dài 3,4, n.

Ví dụ

#include <iostream>
#include<string.h>
using namespace std;
void printPermutations(char *str, char* permutations, int last, int index){
   int i, len = strlen(str);
   for ( i = 0; i < len; i++ ) {
      permutations[index] = str[i] ;
      if (index == last)
         cout<<permutations <<"\t";
      else
         printPermutations (str, permutations, last, index+1);
   }
}
int main() {
   char str[] = "ABC";
   cout<<"All permutations of the string with repetition of "<<str<<" are: "<<endl ;
   int len = strlen(str) ;
   char permutations[len];
   printPermutations (str, permutations, len-1, 0);
   return 0;
}

Đầu ra

All permutations of the string with repetition of ABC are:
AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC