Cho chuỗi độ dài n. In tất cả hoán vị palindrome có thể tạo từ ký tự chuỗi theo thứ tự bảng chữ cái. Nếu không tạo được palindrome in '-1'.
Input: "abcba" Output: abcba bacba
Giải pháp: Tìm palindrome đầu tiên theo thứ tự từ điển, sau đó sinh palindrome tiếp theo bằng next_permutation trên nửa đầu.
Các bước
B1: Đếm tần suất ký tự. B2: Kiểm tra có tạo palindrome được không (tối đa 1 ký tự lẻ). B3: Tạo nửa đầu palindrome, ký tự lẻ (nếu có) ở giữa. B4: In palindrome, dùng next_permutation trên nửa đầu để sinh các palindrome tiếp theo.
Chương trình minh họa
#include <iostream>
#include <string.h>
using namespace std;
const char MAX_CHAR = 26;
void countFreq(char str[], int freq[], int n){
for (int i = 0; i < n; i++) freq[str[i] - 'a']++;
}
bool canMakePalindrome(int freq[], int n){
int count_odd = 0;
for (int i = 0; i < 26; i++) if (freq[i] % 2 != 0) count_odd++;
if (n % 2 == 0) return count_odd == 0;
return count_odd == 1;
}
bool isPalimdrome(char str[], int n){
int freq[26] = {0};
countFreq(str, freq, n);
if (!canMakePalindrome(freq, n)) return false;
char odd_char;
for (int i = 0; i < 26; i++) {
if (freq[i] % 2 != 0) { freq[i]--; odd_char = (char)(i + 'a'); break; }
}
int front = 0, rear = n - 1;
for (int i = 0; i < 26; i++) {
if (freq[i] != 0) {
char ch = (char)(i + 'a');
for (int j = 1; j <= freq[i] / 2; j++) {
str[front++] = ch; str[rear--] = ch;
}
}
}
if (front == rear) str[front] = odd_char;
return true;
}
void reverse(char str[], int i, int j){
while (i < j) { swap(str[i], str[j]); i++; j--; }
}
bool nextPalindrome(char str[], int n){
if (n <= 3) return false;
int mid = n / 2 - 1;
int i, j;
for (i = mid - 1; i >= 0; i--) if (str[i] < str[i + 1]) break;
if (i < 0) return false;
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (str[j] > str[i] && str[j] < str[smallest]) smallest = j;
swap(str[i], str[smallest]);
swap(str[n - i - 1], str[n - smallest - 1]);
reverse(str, i + 1, mid);
if (n % 2 == 0) reverse(str, mid + 1, n - i - 2);
else reverse(str, mid + 2, n - i - 2);
return true;
}
void printAllPalindromes(char str[], int n){
if (!(isPalimdrome(str, n))) { cout << "-1"; return; }
do { cout << str << endl; } while (nextPalindrome(str, n));
}
int main(){
char str[] = "abccba";
int n = strlen(str);
cout << "Danh sách palindrome:\n";
printAllPalindromes(str, n);
return 0;
}
Kết quả
abccba acbbca baccab bcaacb cabbac cbaabc