Print all permutations with repetition of characters
The problem involves generating all possible permutations of a given string where repetition of characters is allowed. This means that each character in the string can appear multiple times in the permutations. This problem can be solved using a recursive approach that systematically explores different combinations of characters.
Problem Statement
Given a string containing characters with possible repetitions, the task is to print all possible permutations of the string.
Example
Let's consider the input string "XYZ". The possible permutations with repetition are:
- "XXX", "XXY", "XXZ"
- "XYX", "XYY", "XYZ"
- "XZX", "XZY", "XZZ"
- "YXX", "YXY", "YXZ"
- "YYX", "YYY", "YYZ"
- "YZX", "YZY", "YZZ"
- "ZXX", "ZXY", "ZXZ"
- "ZYX", "ZYY", "ZYZ"
- "ZZX", "ZZY", "ZZZ"
Idea to Solve
To solve this problem, you can use a recursive approach. Starting with an empty result array, for each character in the given string, you'll add it to the result array and recursively call the permutation function to add the next character. This process will be repeated for each character, forming all possible permutations.
Pseudocode
function allPermutation(str, result, n, size):
for i = 0 to size - 1:
result[n] = str[i]
if n == size - 1:
print result
else:
allPermutation(str, result, n + 1, size)
function findPermutation(str, size):
result[size]
print "Given String", str
allPermutation(str, result, 0, size)
function main():
str = "XYZ"
size = length of str
findPermutation(str, size)
main()
Algorithm Explanation
-
allPermutation(str, result, n, size)
: This function generates all permutations with repetition of characters. It takes several parameters:str
: The input string.result
: An array to store the current permutation being formed.n
: The current index in the result array.size
: The size of the input string.
-
For each character in the input string, it assigns the character to the
result
array at indexn
. -
If
n
reaches the last position in theresult
array (which issize - 1
), it means a permutation has been formed. So, it prints the current permutation. -
If
n
is not at the last position, it recursively calls theallPermutation
function to move on to the next character in the string. -
findPermutation(str, size)
: This function initializes theresult
array and calls theallPermutation
function to generate all permutations with repetition.
Code Solution
// C Program
// Print all permutations with repetition of characters
#include <stdio.h>
// Method which is print all permutations of given string
void allPermutation(char str[], char result[], int n, int size)
{
// Execute loop through by string length
for (int i = 0; i < size; ++i)
{
// Assign current element into result space
result[n] = str[i];
if (n == size - 1)
{
// When n is equal to last position of string
printf("\n %s", result);
}
else
{
// Recursively, finding other permutation
allPermutation(str, result, n + 1, size);
}
}
}
// Handle request to find permutation of repetition characters
void findPermutation(char str[], int size)
{
// Auxiliary space to store permutations result
char result[size];
printf("\n Given String %s", str);
// Print permutation
allPermutation(str, result, 0, size);
}
int main()
{
// Given string is form of array
char str[] = "XYZ";
// Get the size
int size = sizeof(str) / sizeof(str[0]) - 1;
// Test
findPermutation(str, size);
return 0;
}
Output
Given String XYZ
XXX
XXY
XXZ
XYX
XYY
XYZ
XZX
XZY
XZZ
YXX
YXY
YXZ
YYX
YYY
YYZ
YZX
YZY
YZZ
ZXX
ZXY
ZXZ
ZYX
ZYY
ZYZ
ZZX
ZZY
ZZZ
/*
Java Program
Print all permutations with repetition of characters
*/
class Permutation
{
// Method which is print all permutations of given string
public void allPermutation(String str, char[] result, int n, int size)
{
// Execute loop through by string length
for (int i = 0; i < size; ++i)
{
// Assign current element into result space
result[n] = str.charAt(i);
if (n == size - 1)
{
String ans = new String(result);
// When n is equal to last position of string
System.out.print("\n " + ans);
}
else
{
// Recursively, finding other permutation
allPermutation(str, result, n + 1, size);
}
}
}
// Handle request to find permutation of repetition characters
public void findPermutation(String str, int size)
{
System.out.print("\n Given String " + str);
// Use to collect permutation
char[] result = new char[size];
// Print permutation
allPermutation(str, result, 0, size);
}
public static void main(String[] args)
{
Permutation task = new Permutation();
// Given text
String str = "XYZ";
// Get number of characters
int size = str.length();
// Test
task.findPermutation(str, size);
}
}
Output
Given String XYZ
XXX
XXY
XXZ
XYX
XYY
XYZ
XZX
XZY
XZZ
YXX
YXY
YXZ
YYX
YYY
YYZ
YZX
YZY
YZZ
ZXX
ZXY
ZXZ
ZYX
ZYY
ZYZ
ZZX
ZZY
ZZZ
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ Program
Print all permutations with repetition of characters
*/
class Permutation
{
public:
// Method which is print all permutations of given string
void allPermutation(string str, char result[], int n, int size)
{
// Execute loop through by string length
for (int i = 0; i < size; ++i)
{
// Assign current element into result space
result[n] = str[i];
if (n == size - 1)
{
// When n is equal to last position of string
cout << "\n " << result;
}
else
{
// Recursively, finding other permutation
this->allPermutation(str, result, n + 1, size);
}
}
}
// Handle request to find permutation of repetition characters
void findPermutation(string str, int size)
{
cout << "\n Given String " << str;
// Use to collect permutation
char result[size];
// Print permutation
this->allPermutation(str, result, 0, size);
}
};
int main()
{
Permutation task = Permutation();
// Given text
string str = "XYZ";
// Get number of characters
int size = str.length();
// Test
task.findPermutation(str, size);
return 0;
}
Output
Given String XYZ
XXX
XXY
XXZ
XYX
XYY
XYZ
XZX
XZY
XZZ
YXX
YXY
YXZ
YYX
YYY
YYZ
YZX
YZY
YZZ
ZXX
ZXY
ZXZ
ZYX
ZYY
ZYZ
ZZX
ZZY
ZZZ
// Include namespace system
using System;
/*
C# Program
Print all permutations with repetition of characters
*/
public class Permutation
{
// Method which is print all permutations of given string
public void allPermutation(String str, char[] result, int n, int size)
{
// Execute loop through by string length
for (int i = 0; i < size; ++i)
{
// Assign current element into result space
result[n] = str[i];
if (n == size - 1)
{
String ans = new String(result);
// When n is equal to last position of string
Console.Write("\n " + ans);
}
else
{
// Recursively, finding other permutation
allPermutation(str, result, n + 1, size);
}
}
}
// Handle request to find permutation of repetition characters
public void findPermutation(String str, int size)
{
Console.Write("\n Given String " + str);
// Use to collect permutation
char[] result = new char[size];
// Print permutation
allPermutation(str, result, 0, size);
}
public static void Main(String[] args)
{
Permutation task = new Permutation();
// Given text
String str = "XYZ";
// Get number of characters
int size = str.Length;
// Test
task.findPermutation(str, size);
}
}
Output
Given String XYZ
XXX
XXY
XXZ
XYX
XYY
XYZ
XZX
XZY
XZZ
YXX
YXY
YXZ
YYX
YYY
YYZ
YZX
YZY
YZZ
ZXX
ZXY
ZXZ
ZYX
ZYY
ZYZ
ZZX
ZZY
ZZZ
<?php
/*
Php Program
Print all permutations with repetition of characters
*/
class Permutation
{
// Method which is print all permutations of given string
public function allPermutation($str, & $result, $n, $size)
{
// Execute loop through by string length
for ($i = 0; $i < $size; ++$i)
{
// Assign current element into result space
$result[$n] = $str[$i];
if ($n == $size - 1)
{
// When n is equal to last position of string
echo "\n ". implode("",$result);
}
else
{
// Recursively, finding other permutation
$this->allPermutation($str, $result, $n + 1, $size);
}
}
}
// Handle request to find permutation of repetition characters
public function findPermutation($str, $size)
{
echo "\n Given String ". $str;
// Use to collect permutation
$result = array_fill(0, $size, ' ');
// Print permutation
$this->allPermutation($str, $result, 0, $size);
}
}
function main()
{
$task = new Permutation();
// Given text
$str = "XYZ";
// Get number of characters
$size = strlen($str);
$task->findPermutation($str, $size);
}
main();
Output
Given String XYZ
XXX
XXY
XXZ
XYX
XYY
XYZ
XZX
XZY
XZZ
YXX
YXY
YXZ
YYX
YYY
YYZ
YZX
YZY
YZZ
ZXX
ZXY
ZXZ
ZYX
ZYY
ZYZ
ZZX
ZZY
ZZZ
/*
Node Js Program
Print all permutations with repetition of characters
*/
class Permutation
{
// Method which is print all permutations of given string
allPermutation(str, result, n, size)
{
// Execute loop through by string length
for (var i = 0; i < size; ++i)
{
// Assign current element into result space
result[n] = str.charAt(i);
if (n == size - 1)
{
var ans = result.join("");
// When n is equal to last position of string
process.stdout.write("\n " + ans);
}
else
{
// Recursively, finding other permutation
this.allPermutation(str, result, n + 1, size);
}
}
}
// Handle request to find permutation of repetition characters
findPermutation(str, size)
{
process.stdout.write("\n Given String " + str);
// Use to collect permutation
var result = Array(size).fill(' ');
// Print permutation
this.allPermutation(str, result, 0, size);
}
}
function main()
{
var task = new Permutation();
// Given text
var str = "XYZ";
// Get number of characters
var size = str.length;
// Test
task.findPermutation(str, size);
}
main();
Output
Given String XYZ
XXX
XXY
XXZ
XYX
XYY
XYZ
XZX
XZY
XZZ
YXX
YXY
YXZ
YYX
YYY
YYZ
YZX
YZY
YZZ
ZXX
ZXY
ZXZ
ZYX
ZYY
ZYZ
ZZX
ZZY
ZZZ
# Python 3 Program
# Print all permutations with repetition of characters
class Permutation :
# Method which is print all permutations of given string
def allPermutation(self, text, result, n, size) :
# Execute loop through by string length
i = 0
while (i < size) :
# Assign current element into result space
result[n] = text[i]
if (n == size - 1) :
# When n is equal to last position of string
print("\n ", result, end = "")
else :
# Recursively, finding other permutation
self.allPermutation(text, result, n + 1, size)
i += 1
# Handle request to find permutation of repetition characters
def findPermutation(self, text, size) :
print("\n Given String ", text, end = "")
# Use to collect permutation
result = [ ' '] * (size)
# Print permutation
self.allPermutation(text, result, 0, size)
def main() :
task = Permutation()
# Given text
text = "XYZ"
# Get number of characters
size = len(text)
# Test
task.findPermutation(text, size)
if __name__ == "__main__": main()
Output
Given String XYZ
['X', 'X', 'X']
['X', 'X', 'Y']
['X', 'X', 'Z']
['X', 'Y', 'X']
['X', 'Y', 'Y']
['X', 'Y', 'Z']
['X', 'Z', 'X']
['X', 'Z', 'Y']
['X', 'Z', 'Z']
['Y', 'X', 'X']
['Y', 'X', 'Y']
['Y', 'X', 'Z']
['Y', 'Y', 'X']
['Y', 'Y', 'Y']
['Y', 'Y', 'Z']
['Y', 'Z', 'X']
['Y', 'Z', 'Y']
['Y', 'Z', 'Z']
['Z', 'X', 'X']
['Z', 'X', 'Y']
['Z', 'X', 'Z']
['Z', 'Y', 'X']
['Z', 'Y', 'Y']
['Z', 'Y', 'Z']
['Z', 'Z', 'X']
['Z', 'Z', 'Y']
['Z', 'Z', 'Z']
# Ruby Program
# Print all permutations with repetition of characters
class Permutation
# Method which is print all permutations of given string
def allPermutation(str, result, n, size)
# Execute loop through by string length
i = 0
while (i < size)
# Assign current element into result space
result[n] = str[i]
if (n == size - 1)
# When n is equal to last position of string
print("\n ", result)
else
# Recursively, finding other permutation
self.allPermutation(str, result, n + 1, size)
end
i += 1
end
end
# Handle request to find permutation of repetition characters
def findPermutation(str, size)
print("\n Given String ", str)
# Use to collect permutation
result = Array.new(size) { ' '
}
# Print permutation
self.allPermutation(str, result, 0, size)
end
end
def main()
task = Permutation.new()
# Given text
str = "XYZ"
# Get number of characters
size = str.length
# Test
task.findPermutation(str, size)
end
main()
Output
Given String XYZ
["X", "X", "X"]
["X", "X", "Y"]
["X", "X", "Z"]
["X", "Y", "X"]
["X", "Y", "Y"]
["X", "Y", "Z"]
["X", "Z", "X"]
["X", "Z", "Y"]
["X", "Z", "Z"]
["Y", "X", "X"]
["Y", "X", "Y"]
["Y", "X", "Z"]
["Y", "Y", "X"]
["Y", "Y", "Y"]
["Y", "Y", "Z"]
["Y", "Z", "X"]
["Y", "Z", "Y"]
["Y", "Z", "Z"]
["Z", "X", "X"]
["Z", "X", "Y"]
["Z", "X", "Z"]
["Z", "Y", "X"]
["Z", "Y", "Y"]
["Z", "Y", "Z"]
["Z", "Z", "X"]
["Z", "Z", "Y"]
["Z", "Z", "Z"]
/*
Scala Program
Print all permutations with repetition of characters
*/
class Permutation
{
// Method which is print all permutations of given string
def allPermutation(str: String, result: Array[Character], n: Int, size: Int): Unit = {
// Execute loop through by string length
var i: Int = 0;
while (i < size)
{
// Assign current element into result space
result(n) = str.charAt(i);
if (n == size - 1)
{
var ans: String = result.mkString("");
// When n is equal to last position of string
print("\n " + ans);
}
else
{
// Recursively, finding other permutation
this.allPermutation(str, result, n + 1, size);
}
i += 1;
}
}
// Handle request to find permutation of repetition characters
def findPermutation(str: String, size: Int): Unit = {
print("\n Given String " + str);
// Use to collect permutation
var result: Array[Character] = Array.fill[Character](size)(' ');
// Print permutation
this.allPermutation(str, result, 0, size);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Permutation = new Permutation();
// Given text
var str: String = "XYZ";
// Get number of characters
var size: Int = str.length();
// Test
task.findPermutation(str, size);
}
}
Output
Given String XYZ
XXX
XXY
XXZ
XYX
XYY
XYZ
XZX
XZY
XZZ
YXX
YXY
YXZ
YYX
YYY
YYZ
YZX
YZY
YZZ
ZXX
ZXY
ZXZ
ZYX
ZYY
ZYZ
ZZX
ZZY
ZZZ
import Foundation
/*
Swift 4 Program
Print all permutations with repetition of characters
*/
class Permutation
{
// Method which is print all permutations of given string
func allPermutation(_ str: [Character], _ result: inout[Character], _ n: Int, _ size: Int)
{
// Execute loop through by string length
var i: Int = 0;
while (i < size)
{
// Assign current element into result space
result[n] = str[i];
if (n == size - 1)
{
let ans: String = String(result);
// When n is equal to last position of string
print("\n ", ans, terminator: "");
}
else
{
// Recursively, finding other permutation
self.allPermutation(str, &result, n + 1, size);
}
i += 1;
}
}
// Handle request to find permutation of repetition characters
func findPermutation(_ str: String, _ size: Int)
{
print("\n Given String ", str, terminator: "");
// Use to collect permutation
var result: [Character] = Array(repeating: " ", count: size);
// Print permutation
self.allPermutation(Array(str), &result, 0, size);
}
}
func main()
{
let task: Permutation = Permutation();
// Given text
let str: String = "XYZ";
// Get number of characters
let size: Int = str.count;
// Test
task.findPermutation(str, size);
}
main();
Output
Given String XYZ
XXX
XXY
XXZ
XYX
XYY
XYZ
XZX
XZY
XZZ
YXX
YXY
YXZ
YYX
YYY
YYZ
YZX
YZY
YZZ
ZXX
ZXY
ZXZ
ZYX
ZYY
ZYZ
ZZX
ZZY
ZZZ
/*
Kotlin Program
Print all permutations with repetition of characters
*/
class Permutation
{
// Method which is print all permutations of given string
fun allPermutation(str: String, result: Array < Char > , n: Int, size: Int): Unit
{
// Execute loop through by string length
var i: Int = 0;
while (i < size)
{
// Assign current element into result space
result[n] = str.get(i);
if (n == size - 1)
{
var ans: String = result.joinToString(separator = "");
// When n is equal to last position of string
print("\n " + ans);
}
else
{
// Recursively, finding other permutation
this.allPermutation(str, result, n + 1, size);
}
i += 1;
}
}
// Handle request to find permutation of repetition characters
fun findPermutation(str: String, size: Int): Unit
{
print("\n Given String " + str);
// Use to collect permutation
var result: Array < Char > = Array(size)
{
' '
};
// Print permutation
this.allPermutation(str, result, 0, size);
}
}
fun main(args: Array < String > ): Unit
{
var task: Permutation = Permutation();
// Given text
var str: String = "XYZ";
// Get number of characters
var size: Int = str.length;
// Test
task.findPermutation(str, size);
}
Output
Given String XYZ
XXX
XXY
XXZ
XYX
XYY
XYZ
XZX
XZY
XZZ
YXX
YXY
YXZ
YYX
YYY
YYZ
YZX
YZY
YZZ
ZXX
ZXY
ZXZ
ZYX
ZYY
ZYZ
ZZX
ZZY
ZZZ
Time Complexity
The time complexity of this algorithm depends on the number of permutations that need to be generated. In the worst
case, where the string consists of distinct characters, the number of permutations is n^n
, where
n
is the length of the string.
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.
New Comment