พิมพ์ Palindromic Permutations ทั้งหมดของสตริงที่กำหนดในลำดับอักษรใน C++

ในปัญหานี้ เราจะได้รับสตริงขนาด n และต้องพิมพ์ palindromic permutations ทั้งหมดที่เป็นไปได้ที่สร้างจากตัวอักษรของสตริงในลำดับอักษร หากสร้าง palindrome ไม่ได้จากสตริง ให้พิมพ์ '-1'

ตัวอย่างเพื่อความเข้าใจ

Input: string = "abcba"
Output: abcba bacba

ตอนนี้เพื่อแก้ปัญหานี้ เราต้องหา palindromes ทั้งหมดที่เป็นไปได้ และจัดเรียงในลำดับอักษร (lexicographical order) หรืออีกวิธีคือหา lexicographically first palindrome ที่สร้างจากสตริง แล้วหา palindrome ถัดไปตามลำดับ

สำหรับนี้ เราจะทำขั้นตอนดังนี้:

ขั้นตอนที่ 1 - เก็บความถี่ของตัวอักษรทั้งหมดของสตริง

ขั้นตอนที่ 2 - ตรวจสอบว่าสตริงสามารถสร้าง palindrome ได้หรือไม่ ถ้าไม่ได้ PRINT "No palindrome can be formed" และออก มิฉะนั้นทำต่อ:

ขั้นตอนที่ 3 - สร้างสตริงตามตรรกะที่ตัวอักษรที่มีความถี่คู่สร้างสตริง และความถี่คี่จากอีกส่วน และเราจะแซนด์วิช odd string ระหว่าง even string (คือรูปแบบ even_string + odd_string + even_string)

ด้วยวิธีนี้ เราสามารถหา lexicographically first palindrome ได้ แล้วหาตัวถัดไปโดยตรวจสอบ concurrent lexicographical combinations

โปรแกรมตัวอย่าง

#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) {
        if (count_odd > 0)
            return false;
        else
            return true;
    }
    if (count_odd != 1)
        return false;
    return true;
}

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_index = 0, rear_index = 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_index++] = ch;
                str[rear_index--] = ch;
            }
        }
    }
    if (front_index == rear_index)
        str[front_index] = 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 << "The list of palindromes possible is :\n";
    printAllPalindromes(str, n);
    return 0;
}

ผลลัพธ์

The list of palindromes possible is -

abccba acbbca baccab bcaacb cabbac cbaabc