Рубрики

Распечатать все палиндромные перестановки строки

Для данной строки нам нужно вывести все возможные палиндромы, которые можно сгенерировать, используя буквы этой строки.

Примеры:

Input:  str = "aabcb"
Output: abcba bacab

nput:  str = "aabbcadad"
Output: aabdcdbaa aadbcbdaa abadcdaba
        abdacadba adabcbada adbacabda
        baadcdaab badacadab bdaacaadb
        daabcbaad dabacabad dbaacaabd

Генерация палиндрома может быть выполнена с помощью следующих шагов:

  1. Сначала нам нужно проверить, могут ли строковые буквы образовывать палиндром или нет, если нет, то вернуть.
  2. После проверки выше мы можем сделать половину первой строки палиндрома (лексикографически наименьшей), взяв половину частоты каждой буквы данной строки.
  3. Теперь пройдитесь по всем возможным перестановкам этой половины строки и каждый раз добавляйте реверс этой части в конце и добавляйте символ нечетной частоты посередине, если строка имеет нечетную длину, для создания палиндрома.

Ниже приведена реализация C ++.

// C ++ программа для печати всех перестановок палиндрома
// строка.
#include <bits/stdc++.h>

using namespace std;

#define M 26

  
/ * Утилита для подсчета частот и проверки

    может ли письмо сделать палиндром или нет * /

bool isPalin(string str, int* freq)

{

    / * Инициализация частотного массива со всеми нулями * /

    memset(freq, 0, M * sizeof(int));

    int l = str.length();

  

    / * Частота обновления в соответствии с заданной строкой * /

    for (int i = 0; i < l; i++)

        freq[str[i] - 'a']++;

  

    int odd = 0;

  

    / * Цикл для подсчета всего письма с нечетной частотой * /

    for (int i = 0; i < M; i++)

        if (freq[i] % 2 == 1)

            odd++;

  

    / * Состояние палиндрома:

    если длина нечетная, то частота только одной буквы должна быть нечетной

    если длина четная, буквы не должны иметь нечетную частоту * /

    if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))

        return true;

    else

        return false;

}

  
/ * Утилита для обращения строки * /
string reverse(string str)
{

    string rev = str;

    reverse(rev.begin(), rev.end());

    return rev;

}

  
/ * Функция печати всех возможных палиндромов по буквам

    заданная строка * /

void printAllPossiblePalindromes(string str)

{

    int freq[M];

  

    // проверяем, может ли письмо сделать палиндром или нет

    if (!isPalin(str, freq))

        return;

  

    int l = str.length();

  

    // половина будет содержать половину всех палиндромов,

    // поэтому нажимаем половину частоты каждой буквы

    string half = "";

    char oddC;

    for (int i = 0; i < M; i++)

    {

        / * Это условие будет выполнено не более одного раза * /

        if(freq[i] % 2 == 1)

            oddC = i + 'a';

  

        half += string(freq[i] / 2, i + 'a');

    }

  

    / * Палин будет хранить возможные палиндромы один за другим * /

    string palin;

  

    // Теперь перебираем все перестановки половин и добавляем

    // обратная часть в конце.

    // если длина нечетная, то нажатие oddCharacter также в середине

    do

    {

        palin = half;

        if (l % 2 == 1)

            palin += oddC;

        palin += reverse(half);

        cout << palin << endl;

    }

    while (next_permutation(half.begin(), half.end()));

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    string str = "aabbcadad";

    cout << "All palindrome permutations of " << str << endl;

    printAllPossiblePalindromes(str);

    return 0;

}

Выход:

All palindrome permutations of aabbcadad
aabdcdbaa
aadbcbdaa
abadcdaba
abdacadba
adabcbada
adbacabda
baadcdaab
badacadab
bdaacaadb
daabcbaad
dabacabad
dbaacaabd

Иллюстрация:

Let given string is "aabbcadad"

Letters have following frequencies : 
 a(4), b(2), c(1), d(2).

As all letter has even frequency except one we can 
make palindromes with the letter of this string.

Now half part is – aabd

So traversing through all possible permutations of 
this half string and adding odd frequency character 
and reverse of string at the end we get following 
possible palindrome as final result : 
aabdcdbaa   aadbcbdaa   abadcdaba   abdacadba
adabcbada   adbacabda   baadcdaab   badacadab
bdaacaadb   daabcbaad   dabacabad   dbaacaabd

Эта статья предоставлена Уткаршем Триведи. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Распечатать все палиндромные перестановки строки

0.00 (0%) 0 votes