Bir Simli Palindrom Permutasiyaları

Problem bəyanat

"Bir Simli Palindrom Permutasiyaları" problemində bir giriş verdik sim "S". Sətrin simvollarından istifadə edərək yaradıla biləcək bütün mümkün palindromları çap edin.

Giriş Formatı

"S" simli olan ilk və yalnız bir sətir.

Çıxış formatı

Mümkün olan bütün permutasiyaları verilmiş “s” sətrinin sətirinə çap edin.

Məhdudiyyətlər

• 1 <= | s | <= 10
• s [i] aşağı İngilis əlifbası olmalıdır

misal

aabbc

abcba
bacab

Alqoritm

1. Sətir hərflərinin palindrom yarada biləcəyini yoxlayın, əgər palindrom geri qayıda bilməzsə.

• Sıfırlarla sayma massivini başlayın.
• Simvolların sayı ilə tezliyi doldurun.
• Uzunluq təkdirsə, yalnız bir simvol tək saydan ibarət olmalıdır.
• Uzunluq hətta heç bir məktubun tək bir tezliyi olmamalıdır.

2. Giriş paltarının hər bir simvolunun tezliyinin yarısını alaraq ilk palindrom simli simli yarının yarısını leksikoqrafiya baxımından ən kiçik edəcəyik.

3. Yarım simli mümkün olan bütün permütasiyadan keçin və hər dəfə sonunda bu hissənin əksini əlavə edin.

4. Palindromu düzəltmək üçün aranın arasına tək sətir xarakteri əlavə edin.

Həyata keçirilməsi

Bir Simli Palindrom Permutasiyaları üçün C ++ Proqramı

#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 printpalindromes(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; 

  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 s;
  cin>>s;
  printpalindromes(s); 
  return 0; 
}

import java.util.HashMap;
import java.util.Scanner;
class sum
{
    public static boolean isPalin(String str, int freq[]) 
    {
  for(int i=0;i<26;i++)
        {
            freq[i]=0;
        }
  int l = str.length(); 
  for (int i = 0; i < l; i++) 
    freq[str.charAt(i) - 'a']++; 

  int odd = 0; 
  for (int i = 0; i < 26; i++) 
    if (freq[i] % 2 == 1) 
      odd++; 
  if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0)) 
    return true; 
  else
    return false; 
    } 
    public static int isPalindrome(String s, int l, int h)  
    { 
        while(h > l) 
            if(s.charAt(l++) != s.charAt(h--)) 
                return 0; 
        return 1; 
    }
    static char[] swap(String str, int i, int j) 
    { 
        char ch[] = str.toCharArray(); 
        char temp = ch[i]; 
        ch[i] = ch[j]; 
        ch[j] = temp; 
        return ch; 
    }
    
    private static String next_permutation( final String c ) {
    int first = c.charAt(0);
    if ( first == -1 ) return null; 
                
    int toSwap = c.length()-1;
    while(c.charAt(first)>=( c.charAt(toSwap)))
      --toSwap;
    swap(c,first++,toSwap);
    toSwap = c.length() - 1;
    while ( first < toSwap )
      swap( c, first++, toSwap-- );
    return c;
  }
    public static void printpalindromes(String str) 
    { 
  int freq[] = new int[26]; 
  if(!isPalin(str, freq)) 
    return; 
  int l = str.length(); 
  String half = ""; 
        char oddC = 0;
  for(int i=0;i<26;i++) 
  { 
    if(freq[i]%2==1) 
      oddC = (char) (i + 'a'); 
                for(int q=0;q<freq[i]/2;q++)
                {
                    half+=(char) i+'a';
                }
  } 
  String palin;
  do
  { 
    palin = half; 
    if (l % 2 == 1) 
      palin += oddC; 
                StringBuilder x = new StringBuilder();
                x.append(half);
                x.reverse();
    palin +=x; 
    System.out.println(palin);
  } 
  while(next_permutation(half)!=null);
    } 
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
  printpalindromes(s);
    }
}

dababd

abddba
adbbda
baddab
bdaadb
dabbad
dbaabd

Bir Simli Palindrom Permutasiyaları üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n!) hara n verilən sətrin uzunluğunu göstərir. Burada zaman mürəkkəbliyi n !. olan next_permutation funksiyasından istifadə edirik.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.