Posted on by Kalkicode
Code Backtracking

# 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

1. `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.
2. For each character in the input string, it assigns the character to the `result` array at index `n`.

3. If `n` reaches the last position in the `result` array (which is `size - 1`), it means a permutation has been formed. So, it prints the current permutation.

4. If `n` is not at the last position, it recursively calls the `allPermutation` function to move on to the next character in the string.

5. `findPermutation(str, size)`: This function initializes the `result` array and calls the `allPermutation` 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)
{
// Given text
String str = "XYZ";
// Get number of characters
int size = str.length();
// Test
}
}``````

#### 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()
{
// Given text
string str = "XYZ";
// Get number of characters
int size = str.length();
// Test
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)
{
// Given text
String str = "XYZ";
// Get number of characters
int size = str.Length;
// Test
}
}``````

#### 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()
{
// Given text
\$str = "XYZ";
// Get number of characters
\$size = strlen(\$str);
}
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()
{
// Given text
var str = "XYZ";
// Get number of characters
var size = str.length;
// Test
}
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() :
#  Given text
text = "XYZ"
#  Get number of characters
size = len(text)
#  Test

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()
#  Given text
str = "XYZ"
#  Get number of characters
size = str.length
#  Test
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
}
}``````

#### 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()
{
// Given text
let str: String = "XYZ";
// Get number of characters
let size: Int = str.count;
// Test
}
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
{
// Given text
var str: String = "XYZ";
// Get number of characters
var size: Int = str.length;
// Test
}``````

#### 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.

## 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