Permutations of given String
Last Updated :
18 Oct, 2023
Given a string S, the task is to write a program to print all permutations of a given string.
A permutation also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length N has N! permutations.
Examples:
Input: S = “ABC”
Output: “ABC”, “ACB”, “BAC”, “BCA”, “CBA”, “CAB”
Input: S = “XY”
Output: “XY”, “YX”
Print permutations of a given string using backtracking:
Recursion Tree for permutations of string “ABC”
Follow the given steps to solve the problem:
- Create a function permute() with parameters as input string, starting index of the string, ending index of the string
- Call this function with values input string, 0, size of string – 1
- In this function, if the value of L and R is the same then print the same string
- Else run a for loop from L to R and swap the current element in the for loop with the inputString[L]
- Then again call this same function by increasing the value of L by 1
- After that again swap the previously swapped values to initiate backtracking
Below is the implementation of the above approach:
C++14
#include <bits/stdc++.h>
using namespace std;
void permute(string& a, int l, int r)
{
if (l == r)
cout << a << endl;
else {
for (int i = l; i <= r; i++) {
swap(a[l], a[i]);
permute(a, l + 1, r);
swap(a[l], a[i]);
}
}
}
int main()
{
string str = "ABC";
int n = str.size();
permute(str, 0, n - 1);
return 0;
}
|
C
#include <stdio.h>
#include <string.h>
void swap(char* x, char* y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
void permute(char* a, int l, int r)
{
int i;
if (l == r)
printf("%s\n", a);
else {
for (i = l; i <= r; i++) {
swap((a + l), (a + i));
permute(a, l + 1, r);
swap((a + l), (a + i));
}
}
}
int main()
{
char str[] = "ABC";
int n = strlen(str);
permute(str, 0, n - 1);
return 0;
}
|
Java
public class Permutation {
public static void main(String[] args)
{
String str = "ABC";
int n = str.length();
Permutation permutation = new Permutation();
permutation.permute(str, 0, n - 1);
}
private void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else {
for (int i = l; i <= r; i++) {
str = swap(str, l, i);
permute(str, l + 1, r);
str = swap(str, l, i);
}
}
}
/**
* Swap Characters at position
* @param a string value
* @param i position 1
* @param j position 2
* @return swapped string
*/
public String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
}
|
Python3
def toString(List):
return ''.join(List)
def permute(a, l, r):
if l == r:
print(toString(a))
else:
for i in range(l, r):
a[l], a[i] = a[i], a[l]
permute(a, l+1, r)
a[l], a[i] = a[i], a[l]
string = "ABC"
n = len(string)
a = list(string)
permute(a, 0, n)
|
C#
using System;
class GFG {
private static void permute(String str, int l, int r)
{
if (l == r)
Console.WriteLine(str);
else {
for (int i = l; i <= r; i++) {
str = swap(str, l, i);
permute(str, l + 1, r);
str = swap(str, l, i);
}
}
}
public static String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.ToCharArray();
temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
string s = new string(charArray);
return s;
}
public static void Main()
{
String str = "ABC";
int n = str.Length;
permute(str, 0, n - 1);
}
}
|
Javascript
<script>
function permute(str, l, r)
{
if (l == r)
document.write(str+"<br>");
else
{
for (let i = l; i <= r; i++)
{
str = swap(str, l, i);
permute(str, l + 1, r);
str = swap(str, l, i);
}
}
}
function swap(a, i, j)
{
let temp;
let charArray = a.split("");
temp = charArray[i] ;
charArray[i] = charArray[j];
charArray[j] = temp;
return (charArray).join("");
}
let str = "ABC";
let n = str.length;
permute(str, 0, n-1);
</script>
|
PHP
<?php
function permute($str, $l, $r)
{
if ($l == $r)
echo $str. "\n";
else
{
for ($i = $l; $i <= $r; $i++)
{
$str = swap($str, $l, $i);
permute($str, $l + 1, $r);
$str = swap($str, $l, $i);
}
}
}
function swap($a, $i, $j)
{
$temp;
$charArray = str_split($a);
$temp = $charArray[$i] ;
$charArray[$i] = $charArray[$j];
$charArray[$j] = $temp;
return implode($charArray);
}
$str = "ABC";
$n = strlen($str);
permute($str, 0, $n - 1);
?>
|
Output
ABC
ACB
BAC
BCA
CBA
CAB
Time Complexity: O(N * N!) Note that there are N! permutations and it requires O(N) time to print a permutation.
Auxiliary Space: O(R – L)
Note: The above solution prints duplicate permutations if there are repeating characters in the input string. Please see the below link for a solution that prints only distinct permutations even if there are duplicates in input.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...