Cho chuỗi n ký tự, in tất cả hoán vị độ dài n, cho phép lặp ký tự, theo thứ tự bảng chữ cái.
Input: XY Output: XX, XY, YX, YY
Giải pháp: Đệ quy cố định ký tự tại từng vị trí, lặp qua tất cả ký tự của chuỗi gốc.
Chương trình minh họa
#include <iostream>
#include <string.h>
using namespace std;
void printPermutations(char *str, char* perm, int last, int index){
int len = strlen(str);
for (int i = 0; i < len; i++){
perm[index] = str[i];
if (index == last) cout << perm << "\t";
else printPermutations(str, perm, last, index+1);
}
}
int main(){
char str[] = "ABC";
cout << "Tất cả hoán vị có lặp của " << str << ":\n";
int len = strlen(str);
char perm[len];
printPermutations(str, perm, len-1, 0);
return 0;
}
Kết quả
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