Posted on by Kalkicode
Code Backtracking

Print all palindrome permutations of a string

The problem at hand is to generate all possible palindrome permutations of a given string. A palindrome permutation is a rearrangement of characters that forms a palindrome, meaning it reads the same forwards as it does backwards. For example, "abcba" is a palindrome, and its permutations like "ababc" and "bacab" are also palindromes.

Problem Statement

Given a string, the goal is to generate and print all possible palindrome permutations of that string.

Example

Let's consider the string "1231233" to understand the problem. The output of the provided code is as follows:

``````Given text : 1231233
Permutable Palindrome
2313132
3123213
1233321
3213123
1323231
2133312``````

Explanation

• The input string is "1231233".
• The code calculates all unique palindrome permutations of this input string.
• The output contains the unique palindrome permutations found.

Idea to Solve

1. Analyze the input string to determine if it can form a palindrome permutation.
2. Generate a frequency record of characters in the string.
3. Create a partial palindrome by considering half of the characters.
4. Recursively generate the palindrome permutations using the partial palindrome and the middle character (if exists).

Algorithm

1. Calculate the frequency of each character in the input string using a HashMap named `record`.
2. Create an empty HashSet named `result` to store unique palindrome permutations.
3. Initialize two empty strings: `auxiliary` and `middle`.
4. Loop through the character frequencies in the `record`:
• If the character frequency is even, add half of it to the `auxiliary` string.
• If the character frequency is odd, check if `middle` is already set. If not, set `middle` to this character. If it's already set, print a message saying a palindrome is not possible and return.
5. Call the `permutablePalindrome` function with initial arguments: `result`, `auxiliary`, `middle`, `0`, and `n / 2`.
6. In the `permutablePalindrome` function:
• If the `index` is greater than `n`, return.
• If the `index` equals `n`, construct the full palindrome permutation using `auxiliary`, `middle`, and its reverse. Add it to the `result` if not already present.
• For each character from `index` to `n - 1`, swap the characters at positions `index` and `i` in the `auxiliary` string.
• Recursively call `permutablePalindrome` with the updated `auxiliary`, keeping the `middle` and other arguments the same.
• Swap the characters back to their original positions in the `auxiliary` string.
7. Print the original text and all the unique palindrome permutations stored in the `result`.

Code Solution

``````import java.util.HashMap;
import java.util.HashSet;
/*
Java program for
Print all palindrome permutations of a string
*/
public class Palindrome
{
public String reverseOrder(String result)
{
int n = result.length();
String text = "";
for (int i = n - 1; i >= 0; --i)
{
text = text + result.charAt(i);
}
return text;
}
//Swapping two string elements by index
public String swap(String text, int size, int a, int b)
{
//Check valid location of swap element
if ((a >= 0 && a < size) && (b >= 0 && b < size))
{
//Get first character
char first = text.charAt(a);
//Get second character
char second = text.charAt(b);
//Put character
text = text.substring(0, b) + first + text.substring(b + 1);
text = text.substring(0, a) + second + text.substring(a + 1);
}
return text;
}
// Method which is print all Palindrome permutation of given text
public void permutablePalindrome(HashSet < String > result, String text, String middle, int index, int n)
{
if (index > n)
{
return;
}
if (index == n)
{
String value = text + middle + this.reverseOrder(text);
if (result.contains(value) == false)
{
}
return;
}
for (int i = index; i < n; ++i)
{
// swap char element
text = swap(text, n, i, index);
permutablePalindrome(result, text, middle, index + 1, n);
// swap char element
text = swap(text, n, i, index);
}
}
public void permutation(String text)
{
// Use to count frequency of text character
HashMap < Character, Integer > record = new HashMap < Character, Integer > ();
// Use to collect unique permutations
HashSet < String > result = new HashSet < String > ();
// Auxiliary variable
String auxiliary = "";
String middle = "";
// Get number of character
int n = text.length();
// Count frequency of character in given text
for (int i = 0; i < n; ++i)
{
if (record.containsKey(text.charAt(i)))
{
record.put(text.charAt(i), record.get(text.charAt(i)) + 1);
}
else
{
record.put(text.charAt(i), 1);
}
}
// Check that given string can be a palindrome permutations or not
for (char k: record.keySet())
{
int temp = record.get(k) / 2;
while (temp > 0)
{
auxiliary += k;
temp--;
}
if ((record.get(k) % 2) != 0)
{
if (middle.equals(""))
{
// When middle element exists
// Single digit
middle += k;
}
else
{
System.out.print("Palindrome not possible in given text : " + text);
return;
}
}
}
permutablePalindrome(result, auxiliary, middle, 0, n / 2);
// Display given text
System.out.println("Given text : " + text);
System.out.println("Permutable Palindrome ");
// Display result
for (String value: result)
{
System.out.println(value);
}
}
public static void main(String[] args)
{
// Test Case
}
}``````

Output

``````Given text : 1231233
Permutable Palindrome
2313132
3123213
1233321
3213123
1323231
2133312
Given text : cabababacb
Permutable Palindrome
abcabbacba
aabbccbbaa
bacabbacab
acbbaabbca
bbcaaaacbb
bbaaccaabb
abacbbcaba
bcaabbaacb
baacbbcaab
cabbaabbac
cbaabbaabc
bbacaacabb
aacbbbbcaa
abbaccabba
acbabbabca
abcbaabcba
ababccbaba
babaccabab
aabcbbcbaa
abbcaacbba
acabbbbaca
bacbaabcab
bcbaaaabcb
baabccbaab
cababbabac
babcaacbab
bcabaabacb
cbbaaaabbc
caabbbbaac
cbabaababc``````
``````// Include header file
#include <iostream>
#include <set>
#include <string>
#include <unordered_map>

using namespace std;
/*
C++ program for
Print all palindrome permutations of a string
*/
class Palindrome
{
public: string reverseOrder(string result)
{
int n = result.length();
string text = "";
for (int i = n - 1; i >= 0; --i)
{
text = text  +  result[i];
}
return text;
}
//Swap the string element of given indexes
string swap(string text,int size,int a,int b)
{
if((a>=0 && a<size)  && (b >= 0 && b < size))
{
//When valid a and b location
char temp = text[a];
text[a] = text[b];
text[b] = temp;

}
//return modified result
return text;
}
// Method which is print all Palindrome permutation of given text
void permutablePalindrome(set < string > &result, string text, string middle, int index, int n)
{
if (index > n)
{
return;
}
if (index == n)
{
string value = text  +  middle  +  this->reverseOrder(text);
if (result.find(value) == result.end() )
{
result.insert(value);
}
return;
}
for (int i = index; i < n; ++i)
{
// swap char element
text = this->swap(text, n, i, index);

this->permutablePalindrome(result, text, middle, index + 1, n);
// swap char element
text = this->swap(text, n, i, index);
}
}
void permutation(string text)
{
// Use to count frequency of text character
unordered_map < char, int > record;
// Use to collect unique permutations
set < string > result;
// Auxiliary variable
string auxiliary = "";
string middle = "";
// Get number of character
int n = text.length();
// Count frequency of character in given text
for (int i = 0; i < n; ++i)
{
if (record.find(text[i]) != record.end())
{
record[text[i]] = record[text[i]] + 1;
}
else
{
record[text[i]] = 1;
}
}
// Check that given string can be a palindrome permutations or not
for (auto &k: record)
{
int temp = (k.second / 2);
while (temp > 0)
{
auxiliary += k.first;
temp--;
}
if ((k.second % 2) != 0)
{
if (middle.compare("") == 0)
{
// When middle element exists
// Single digit
middle = k.first;
}
else
{
cout << "Palindrome not possible in given text : " << text;
return;
}
}
}
this->permutablePalindrome(result, auxiliary, middle, 0, n / 2);
// Display given text
cout << "Given text : " << text << endl;
cout << "Permutable Palindrome " << endl;
// Display result
for (auto &value : result)
{
cout << value << endl;
}
}
};
int main()
{
// Test Case
return 0;
}``````

Output

``````Given text : 1231233
Permutable Palindrome
1233321
1323231
2133312
2313132
3123213
3213123
Given text : cabababacb
Permutable Palindrome
aabbccbbaa
aabcbbcbaa
aacbbbbcaa
ababccbaba
abacbbcaba
abbaccabba
abbcaacbba
abcabbacba
abcbaabcba
acabbbbaca
acbabbabca
acbbaabbca
baabccbaab
baacbbcaab
babaccabab
babcaacbab
bacabbacab
bacbaabcab
bbaaccaabb
bbacaacabb
bbcaaaacbb
bcaabbaacb
bcabaabacb
bcbaaaabcb
caabbbbaac
cababbabac
cabbaabbac
cbaabbaabc
cbabaababc
cbbaaaabbc``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program for
Print all palindrome permutations of a string
*/
public class Palindrome
{
public String reverseOrder(String result)
{
int n = result.Length;
String text = "";
for (int i = n - 1; i >= 0; --i)
{
text = text + result[i];
}
return text;
}
//Swapping two string elements by index
public String swap(String text, int size, int a, int b)
{
//Check valid location of swap element
if ((a >= 0 && a < size) && (b >= 0 && b < size))
{
//Get first character
char first = text[a];
//Get second character
char second = text[b];
//Put character
text = text.Substring(0, b) + first + text.Substring(b + 1);
text = text.Substring(0, a) + second + text.Substring(a + 1);
}
return text;
}
// Method which is print all Palindrome permutation of given text
public void permutablePalindrome(HashSet < string > result,
String text, String middle,
int index, int n)
{
if (index > n)
{
return;
}
if (index == n)
{
String value = text + middle + this.reverseOrder(text);
if (result.Contains(value) == false)
{
}
return;
}
for (int i = index; i < n; ++i)
{
// swap char element
text = this.swap(text, n, i, index);
this.permutablePalindrome(result, text, middle, index + 1, n);
// swap char element
text = this.swap(text, n, i, index);
}
}
public void permutation(String text)
{
// Use to count frequency of text character
Dictionary < char, int > record = new Dictionary < char, int > ();
// Use to collect unique permutations
HashSet < string > result = new HashSet < string > ();
// Auxiliary variable
String auxiliary = "";
String middle = "";
// Get number of character
int n = text.Length;
// Count frequency of character in given text
for (int i = 0; i < n; ++i)
{
if (record.ContainsKey(text[i]))
{
record[text[i]] = record[text[i]] + 1;
}
else
{
}
}
// Check that given string can be a palindrome permutations or not
foreach(KeyValuePair < char, int > k in record)
{
int temp = k.Value / 2;
while (temp > 0)
{
auxiliary += k.Key;
temp--;
}
if ((k.Value % 2) != 0)
{
if (middle.Equals(""))
{
// When middle element exists
// Single digit
middle += k.Key;
}
else
{
Console.Write("Palindrome not possible in given text : " +
text);
return;
}
}
}
this.permutablePalindrome(result, auxiliary, middle, 0, n / 2);
// Display given text
Console.WriteLine("Given text : " + text);
Console.WriteLine("Permutable Palindrome ");
// Display result
foreach(String value in result)
{
Console.WriteLine(value);
}
}
public static void Main(String[] args)
{
// Test Case
}
}``````

Output

``````Given text : 1231233
Permutable Palindrome
1233321
1323231
2133312
2313132
3213123
3123213
Given text : cabababacb
Permutable Palindrome
caabbbbaac
cababbabac
cabbaabbac
cbaabbaabc
cbabaababc
cbbaaaabbc
acabbbbaca
acbabbabca
acbbaabbca
aacbbbbcaa
aabcbbcbaa
aabbccbbaa
abacbbcaba
ababccbaba
abcabbacba
abcbaabcba
abbcaacbba
abbaccabba
baacbbcaab
baabccbaab
bacabbacab
bacbaabcab
babcaacbab
babaccabab
bcaabbaacb
bcabaabacb
bcbaaaabcb
bbacaacabb
bbaaccaabb
bbcaaaacbb``````
``````<?php
/*
Php program for
Print all palindrome permutations of a string
*/
class Palindrome
{
public function reverseOrder(\$result)
{
\$n = strlen(\$result);
\$text = "";
for (\$i = \$n - 1; \$i >= 0; --\$i)
{
\$text = \$text.strval(\$result[\$i]);
}
return \$text;
}
//Swapping two string elements by index
public  function swap(\$text, \$size, \$a, \$b) {
//Check valid location of swap element

if ((\$a >= 0 && \$a < \$size) && (\$b >= 0 && \$b < \$size)) {
//Get first character
\$first = \$text[\$a];
//Get second character
\$second = \$text[\$b];
//Put character
\$text = substr(\$text,0, \$b-strlen(\$text)) . \$first .substr(\$text,\$b+1 );

\$text = substr(\$text,0, \$a-strlen(\$text)) . \$second .substr(\$text,\$a+1 );
}
return \$text;
}

// Method which is print all Palindrome permutation of given text
public	function permutablePalindrome(&\$result, \$text, \$middle, \$index, \$n)
{
if (\$index > \$n)
{
return;
}
if (\$index == \$n)
{
\$value = \$text.\$middle.\$this->reverseOrder(\$text);
if (in_array(\$value, \$result, TRUE) == false)
{
\$result[] = \$value;

}
return;
}
for (\$i = \$index; \$i < \$n; ++\$i)
{
// swap char element
\$text = \$this->swap(\$text, \$n, \$i, \$index);
\$this->permutablePalindrome(
\$result, \$text, \$middle, \$index + 1, \$n
);
// swap char element
\$text = \$this->swap(\$text, \$n, \$i, \$index);
}
}
public	function permutation(\$text)
{
// Use to count frequency of text character
\$record = array();
// Use to collect unique permutations
\$result = array();
// Auxiliary variable
\$auxiliary = "";
\$middle = "";
// Get number of character
\$n = strlen(\$text);
// Count frequency of character in given text
for (\$i = 0; \$i < \$n; ++\$i)
{
if (array_key_exists(\$text[\$i], \$record))
{
\$record[\$text[\$i]] = \$record[\$text[\$i]] + 1;
}
else
{
\$record[\$text[\$i]] = 1;
}
}
// Check that given string can be a palindrome permutations or not
foreach(\$record as \$key => \$value)
{
\$temp = (int)(\$value / 2);
while (\$temp > 0)
{
\$auxiliary .= \$key;
\$temp--;
}
if ((\$value % 2) != 0)
{
if ((strcmp(\$middle, "") == 0))
{
// When middle element exists
// Single digit
\$middle .= \$key;
}
else
{
echo("Palindrome not possible in given text : ".\$text);
return;
}
}
}
\$this->permutablePalindrome(\$result, \$auxiliary,
\$middle, 0, (int)(\$n / 2));
// Display given text
echo("Given text : ".\$text."\n");
echo("Permutable Palindrome "."\n");
// Display result
foreach(\$result as \$key => \$value)
{
echo(\$value."\n");
}
}
}

function main()
{
// Test Case
}
main();``````

Output

``````Given text : 1231233
Permutable Palindrome
1233321
1323231
2133312
2313132
3213123
3123213
Given text : cabababacb
Permutable Palindrome
caabbbbaac
cababbabac
cabbaabbac
cbaabbaabc
cbabaababc
cbbaaaabbc
acabbbbaca
acbabbabca
acbbaabbca
aacbbbbcaa
aabcbbcbaa
aabbccbbaa
abacbbcaba
ababccbaba
abcabbacba
abcbaabcba
abbcaacbba
abbaccabba
baacbbcaab
baabccbaab
bacabbacab
bacbaabcab
babcaacbab
babaccabab
bcaabbaacb
bcabaabacb
bcbaaaabcb
bbacaacabb
bbaaccaabb
bbcaaaacbb``````
``````/*
Node JS program for
Print all palindrome permutations of a string
*/
class Palindrome
{
reverseOrder(result)
{
var n = result.length;
var text = "";
for (var i = n - 1; i >= 0; --i)
{
text = text + result.charAt(i);
}
return text;
}
//Swapping two string elements by index
swap(text, size, a, b)
{
//Check valid location of swap element
if ((a >= 0 && a < size) && (b >= 0 && b < size))
{
//Get first character
var first = text.charAt(a);
//Get second character
var second = text.charAt(b);
//Put character
text = text.substring(0, b) + first + text.substring(b + 1);
text = text.substring(0, a) + second + text.substring(a + 1);
}
return text;
}
// Method which is print all Palindrome permutation of given text
permutablePalindrome(result, text, middle, index, n)
{
if (index > n)
{
return;
}
if (index == n)
{
var value = text + middle + this.reverseOrder(text);
if (result.has(value) == false)
{
}
return;
}
for (var i = index; i < n; ++i)
{
// swap char element
text = this.swap(text, n, i, index);
this.permutablePalindrome(result, text, middle, index + 1, n);
// swap char element
text = this.swap(text, n, i, index);
}
}
permutation(text)
{
// Use to count frequency of text character
var record = new Map();
// Use to collect unique permutations
var result = new Set();
// Auxiliary variable
var auxiliary = "";
var middle = "";
// Get number of character
var n = text.length;
// Count frequency of character in given text
for (var i = 0; i < n; ++i)
{
if (record.has(text.charAt(i)))
{
record.set(text.charAt(i), record.get(text.charAt(i)) + 1);
}
else
{
record.set(text.charAt(i), 1);
}
}
// Check that given string can be a palindrome permutations or not
for (let [key, value] of record)
{
var temp = parseInt(value / 2);
while (temp > 0)
{
auxiliary += key;
temp--;
}
if ((value % 2) != 0)
{
if ((middle.localeCompare("") == 0))
{
// When middle element exists
// Single digit
middle += key;
}
else
{
process.stdout.write(
"Palindrome not possible in given text : " + text
);
return;
}
}
}
this.permutablePalindrome(
result, auxiliary, middle, 0, parseInt(n / 2)
);
// Display given text
console.log("Given text : " + text);
console.log("Permutable Palindrome ");
// Display result
for (let value of result)
{
console.log(value);
}
}
}

function main()
{
// Test Case
}
main();``````

Output

``````Given text : 1231233
Permutable Palindrome
1233321
1323231
2133312
2313132
3213123
3123213
Given text : cabababacb
Permutable Palindrome
caabbbbaac
cababbabac
cabbaabbac
cbaabbaabc
cbabaababc
cbbaaaabbc
acabbbbaca
acbabbabca
acbbaabbca
aacbbbbcaa
aabcbbcbaa
aabbccbbaa
abacbbcaba
ababccbaba
abcabbacba
abcbaabcba
abbcaacbba
abbaccabba
baacbbcaab
baabccbaab
bacabbacab
bacbaabcab
babcaacbab
babaccabab
bcaabbaacb
bcabaabacb
bcbaaaabcb
bbacaacabb
bbaaccaabb
bbcaaaacbb``````
``````#    Python 3 program for
#    Print all palindrome permutations of a string
class Palindrome :
def reverseOrder(self, result) :
n = len(result)
text = ""
i = n - 1
while (i >= 0) :
text = text + str(result[i])
i -= 1

return text

# Swapping two string elements by index

def swap(self, text, size, a, b) :
# Check valid location of swap element
if ((a >= 0 and a < size) and(b >= 0 and b < size)) :
data = list(text)
data[a],data[b] = data[b],data[a]
return ''.join(data)

return text

#  Method which is print all Palindrome permutation of given text
def permutablePalindrome(self, result, text, middle, index, n) :
if (index > n) :
return

if (index == n) :
value = text + middle + self.reverseOrder(text)
if (value in result ) == False :

return

i = index
while (i < n) :
# swap the list element
text = self.swap(text, n, i, index)
self.permutablePalindrome(result, text, middle, index + 1, n)
# swap the list element
text = self.swap(text, n, i, index)
i += 1

def permutation(self, text) :
#  Use to count frequency of text character
record = dict()
#  Use to collect unique permutations
result = set()
#  Auxiliary variable
auxiliary = ""
middle = ""
#  Get number of character
n = len(text)
i = 0
#  Count frequency of character in given text
while (i < n) :
if ((text[i] in record.keys())) :
record[text[i]] = record.get(text[i]) + 1
else :
record[text[i]] = 1

i += 1

for key, value in record.items() :
temp = int(value / 2)
while (temp > 0) :
auxiliary += key
temp -= 1

if ((value % 2) != 0) :
if (middle == "") :
#  When middle element exists
#  Single digit
middle += key
else :
print("Palindrome not possible in given text : ",
text, end = "")
return

self.permutablePalindrome(result,
auxiliary,
middle, 0,
int(n / 2))
#  Display given text
print("Given text : ", text)
print("Permutable Palindrome ")
for value in result :
print(value)

def main() :
#  Test Case

if __name__ == "__main__": main()``````

Output

``````Given text :  1231233
Permutable Palindrome
1233321
3123213
2133312
2313132
3213123
1323231
Given text :  cabababacb
Permutable Palindrome
ababccbaba
abcabbacba
cababbabac
aabcbbcbaa
caabbbbaac
bcabaabacb
cbbaaaabbc
aabbccbbaa
bacabbacab
acbbaabbca
bacbaabcab
abbcaacbba
baabccbaab
acabbbbaca
acbabbabca
bcaabbaacb
bcbaaaabcb
abcbaabcba
babcaacbab
cbabaababc
bbacaacabb
abacbbcaba
cabbaabbac
cbaabbaabc
bbcaaaacbb
babaccabab
aacbbbbcaa
baacbbcaab
bbaaccaabb
abbaccabba``````
``````require 'set'
#    Ruby program for
#    Print all palindrome permutations of a string
class Palindrome
def reverseOrder(result)
n = result.length
text = ""
i = n - 1
while (i >= 0)
text = text + result[i].to_s
i -= 1
end

return text
end

# Swapping two string elements by index
def swap(text, size, a, b)
# Check valid location of swap element
if ((a >= 0 && a < size) && (b >= 0 && b < size))
# Get first character
first = text[a]
text[a]=text[b]
text[b]=first
end
return text
end

#  Method which is print all Palindrome permutation of given text
def permutablePalindrome(result, text, middle, index, n)
if (index > n)
return
end

if (index == n)
value = text + middle + self.reverseOrder(text)
if (result.include?(value) == false)
end

return
end

i = index
while (i < n)
#  swap char element
text = self.swap(text, n, i, index)
self.permutablePalindrome(result, text, middle, index + 1, n)
#  swap char element
text = self.swap(text, n, i, index)
i += 1
end

end

def permutation(text)
#  Use to count frequency of text character
record = Hash.new()
#  Use to collect unique permutations
result = SortedSet.new()
#  Auxiliary variable
auxiliary = ""
middle = ""
#  Get number of character
n = text.length
i = 0
#  Count frequency of character in given text
while (i < n)
if (record.key?(text[i]))
record[text[i]] = record[text[i]] + 1
else

record[text[i]] = 1
end

i += 1
end

#  Check that given string can be a palindrome permutations or not
record.each { | key, value | temp = value / 2
while (temp > 0)
auxiliary += key
temp -= 1
end

if ((value % 2) != 0)
if (middle === "")
#  When middle element exists
#  Single digit
middle += key
else

print("Palindrome not possible in given text : ", text)
return
end

end

}
self.permutablePalindrome(result, auxiliary, middle, 0, n / 2)
#  Display given text
print("Given text : ", text, "\n")
print("Permutable Palindrome ", "\n")
#  Display result
result.each do |value|
print(value, "\n")
end

end

end

def main()
#  Test Case
end

main()``````

Output

``````Given text : 1231233
Permutable Palindrome
1233321
1323231
2133312
2313132
3123213
3213123
Given text : cabababacb
Permutable Palindrome
aabbccbbaa
aabcbbcbaa
aacbbbbcaa
ababccbaba
abacbbcaba
abbaccabba
abbcaacbba
abcabbacba
abcbaabcba
acabbbbaca
acbabbabca
acbbaabbca
baabccbaab
baacbbcaab
babaccabab
babcaacbab
bacabbacab
bacbaabcab
bbaaccaabb
bbacaacabb
bbcaaaacbb
bcaabbaacb
bcabaabacb
bcbaaaabcb
caabbbbaac
cababbabac
cabbaabbac
cbaabbaabc
cbabaababc
cbbaaaabbc
``````
``````import scala.collection.mutable._;
/*
Scala program for
Print all palindrome permutations of a string
*/
class Palindrome()
{
def reverseOrder(result: String): String = {
var n: Int = result.length();
var text: String = "";
var i: Int = n - 1;
while (i >= 0)
{
text = text + result.charAt(i).toString();
i -= 1;
}
return text;
}
//Swapping two string elements by index
def swap(info: String, size: Int, a: Int, b: Int): String = {
//Check valid location of swap element
var text = info;
if ((a >= 0 && a < size) && (b >= 0 && b < size)) {
//Get first character
val first: Char = text(a);

//Get second character
val second: Char = text(b);

//Put character
text = text.substring(0, b) + first + text.substring(b + 1);
text = text.substring(0, a) + second + text.substring(a + 1);
}
return text;
}
// Method which is print all Palindrome permutation of given text
def permutablePalindrome(result: Set[String], text: String, middle: String, index: Int, n: Int): Unit = {
if (index > n)
{
return;
}
if (index == n)
{
var value: String = text + middle + this.reverseOrder(text);
if (result.contains(value) == false)
{
}
return;
}
var i: Int = index;
var new_str = text;
while (i < n)
{
//  swap char element
new_str = swap(new_str, n, i, index);
permutablePalindrome(result, new_str, middle, index + 1, n);
//  swap char element
new_str = swap(new_str, n, i, index);
i += 1;
}
}
def permutation(text: String): Unit = {
// Use to count frequency of text character
var record: HashMap[Character, Int] = new HashMap[Character, Int]();
// Use to collect unique permutations
var result: Set[String] = Set();
// Auxiliary variable
var auxiliary: String = "";
var middle: String = "";
// Get number of character
var n: Int = text.length();
var i: Int = 0;
// Count frequency of character in given text
while (i < n)
{
if (record.contains(text.charAt(i)))
{
}
else
{
}
i += 1;
}
// Check that given string can be a palindrome permutations or not
for((key,value) <- record)
{
var temp: Int = value / 2;
while (temp > 0)
{
auxiliary += key;
temp -= 1;
}
if ((value % 2) != 0)
{
if (middle.equals(""))
{
// When middle element exists
// Single digit
middle += key;
}
else
{
print("Palindrome not possible in given text : " + text);
return;
}
}
}
permutablePalindrome(result, auxiliary, middle, 0, n / 2);
// Display given text
println("Given text : " + text);
println("Permutable Palindrome ");
// Display result
for (value <- result)
{
println(value);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Palindrome = new Palindrome();
// Test Case
}
}``````

Output

``````Given text : 1231233
Permutable Palindrome
2313132
3123213
3213123
1233321
1323231
2133312
Given text : cabababacb
Permutable Palindrome
abcabbacba
aabbccbbaa
bacabbacab
acbbaabbca
bbcaaaacbb
bbaaccaabb
abacbbcaba
bcaabbaacb
baacbbcaab
cbaabbaabc
cabbaabbac
bbacaacabb
abbaccabba
aacbbbbcaa
acbabbabca
abcbaabcba
ababccbaba
babaccabab
aabcbbcbaa
bacbaabcab
acabbbbaca
abbcaacbba
bcbaaaabcb
baabccbaab
cababbabac
babcaacbab
cbbaaaabbc
bcabaabacb
caabbbbaac
cbabaababc``````
``````import Foundation;
/*
Swift 4 program for
Print all palindrome permutations of a string
*/
class Palindrome
{
func reverseOrder(_ result: String) -> String
{
let n: Int = result.count;
var text: String = "";
var i: Int = n - 1;
let data = Array(result);
while (i >= 0)
{
text = text + String(data[i]);
i -= 1;
}
return text;
}
//Swapping two string elements by index
func swap(_ text: String, _ size: Int, _ a: Int, _ b: Int) -> String
{
//Check valid location of swap element
if ((a >= 0 && a < size) && (b >= 0 && b < size))
{
var result = Array(text)

(result[a],result[b]) = (result[b] ,result[a])

return String(result)
}
else
{
return text;
}

}
// Method which is print all Palindrome permutation of given text
func permutablePalindrome(_ result: inout Set<String>,
_ text: String, _ middle: String, _ index: Int, _ n: Int)
{
if (index > n)
{
return;
}
if (index == n)
{
let value: String = text + middle + self.reverseOrder(text);

result.insert(value);

return;
}
var i: Int = index;
var data = text;
while (i < n)
{

//  swap char element
data = self.swap(data, n, i, index);
self.permutablePalindrome(&result, data, middle, index + 1, n);
//  swap char element
data = self.swap(data, n, i, index);
i += 1;
}
}
func permutation(_ data: String)
{	let text = Array(data);
// Use to count frequency of text character
var record = [Character : Int]();
// Use to collect unique permutations
var result = Set<String>()
// Auxiliary variable
var auxiliary: String = "";
var middle: String = "";
// Get number of character
let n: Int = text.count;
var i: Int = 0;
// Count frequency of character in given text
while (i < n)
{
if (record.keys.contains(text[i]))
{
record[text[i]] = record[text[i]]! + 1;
}
else
{
record[text[i]] = 1;
}
i += 1;
}
// Check that given string can be a palindrome permutations or not
for (key, value) in record
{
var temp: Int = value / 2;
while (temp > 0)
{
auxiliary += String(key);
temp -= 1;
}
if ((value % 2)  != 0)
{
if (middle == "")
{
// When middle element exists
// Single digit
middle += String(key);
}
else
{
print("Palindrome not possible in given text : ",
text, terminator: "");
return;
}
}
}
self.permutablePalindrome(&result, auxiliary, middle, 0, n / 2);
// Display given text
print("Given text : ", data);
print("Permutable Palindrome ");
// Display result
for value in result
{
print(value);
}
}
}
func main()
{
// Test Case
}
main();``````

Output

``````Given text :  1231233
Permutable Palindrome
1233321
3213123
1323231
2313132
2133312
3123213
Given text :  cabababacb
Permutable Palindrome
bacabbacab
caabbbbaac
babcaacbab
babaccabab
bbaaccaabb
abbcaacbba
abcbaabcba
bcbaaaabcb
bbcaaaacbb
cbabaababc
abacbbcaba
bbacaacabb
baabccbaab
aacbbbbcaa
acbabbabca
ababccbaba
aabbccbbaa
baacbbcaab
bacbaabcab
bcabaabacb
acabbbbaca
cababbabac
cbbaaaabbc
bcaabbaacb
abbaccabba
aabcbbcbaa
cabbaabbac
abcabbacba
cbaabbaabc
acbbaabbca``````
``````/*
Kotlin program for
Print all palindrome permutations of a string
*/
class Palindrome
{
fun reverseOrder(result: String): String
{
val n: Int = result.length;
var text: String = "";
var i: Int = n - 1;
while (i >= 0)
{
text = text + result.get(i).toString();
i -= 1;
}
return text;
}
//Swapping two string elements by index
fun swap(text: String, size: Int, a: Int, b: Int): String
{
//Check valid location of swap element
if ((a >= 0 && a < size) && (b >= 0 && b < size))
{
//Get first character
val first: Char = text.get(a);
//Get second character
val second: Char = text.get(b);
var result = text;
//Put character
result = result.substring(0, b) + first.toString() +
result.substring(b + 1);
result = result.substring(0, a) + second.toString() +
result.substring(a + 1);
return result;
}
return text;
}
// Method which is print all Palindrome permutation of given text
fun permutablePalindrome(result: MutableSet <String>,
text : String, middle: String,
index: Int, n: Int): Unit
{
if (index > n)
{
return;
}
if (index == n)
{
val value: String = text + middle + this.reverseOrder(text);

return;
}
var i: Int = index;
var data = text;
while (i < n)
{
// swap char element
data = this.swap(data, n, i, index);
this.permutablePalindrome(result, data, middle, index + 1, n);
// swap char element
data = this.swap(data, n, i, index);
i += 1;
}
}
fun permutation(text: String): Unit
{
// Use to count frequency of text character
var record = mutableMapOf<Char, Int>();
// Use to collect unique permutations
var result: MutableSet <String> = mutableSetOf <String> ();
// Auxiliary variable
var auxiliary: String = "";
var middle: String = "";
// Get number of character
val n: Int = text.length;
var i: Int = 0;
// Count frequency of character in given text
while (i < n)
{
if (record.containsKey(text.get(i)))
{
record.put(text.get(i), record.getValue(text.get(i)) + 1);
}
else
{
record.put(text.get(i), 1);
}
i += 1;
}
// Check that given string can be a palindrome permutations or not
for ((key, value) in record)
{
var temp: Int = value / 2;
while (temp > 0)
{
auxiliary += key;
temp -= 1;
}
if ((value % 2) != 0)
{
if (middle.equals(""))
{
// When middle element exists
// Single digit
middle += key;
}
else
{
print("Palindrome not possible in given text : " + text);
return;
}
}
}
this.permutablePalindrome(result, auxiliary, middle, 0, n / 2);
// Display given text
println("Given text : " + text);
println("Permutable Palindrome ");
// Display result
for (value in result)
{
println(value);
}
}
}
fun main(args: Array < String > ): Unit
{
// Test Case
}``````

Output

``````Given text : 1231233
Permutable Palindrome
1233321
1323231
2133312
2313132
3213123
3123213
Given text : cabababacb
Permutable Palindrome
caabbbbaac
cababbabac
cabbaabbac
cbaabbaabc
cbabaababc
cbbaaaabbc
acabbbbaca
acbabbabca
acbbaabbca
aacbbbbcaa
aabcbbcbaa
aabbccbbaa
abacbbcaba
ababccbaba
abcabbacba
abcbaabcba
abbcaacbba
abbaccabba
baacbbcaab
baabccbaab
bacabbacab
bacbaabcab
babcaacbab
babaccabab
bcaabbaacb
bcabaabacb
bcbaaaabcb
bbacaacabb
bbaaccaabb
bbcaaaacbb``````

Time Complexity

The time complexity of this algorithm depends on the number of permutations generated. In the worst case, where all characters have distinct frequencies, the algorithm generates `n!` permutations, where `n` is the length of the input string. Generating each permutation takes `O(n)` time due to swapping characters. Therefore, the overall time complexity is `O(n * n!)`.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post