Posted on June 21, 2021 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

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 index n.
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.
If n is not at the last position, it recursively calls the allPermutation function to move on to the next character in the string.
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)
	{
		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.

Print all permutations with repetition of characters

Problem Statement

Example

Idea to Solve

Pseudocode

Algorithm Explanation

Code Solution

Output

Output

Output

Output

Output

Output

Output

Output

Output

Output

Output

Time Complexity

Comment

New Comment