Print all permutations of a string
Permutations are arrangements of objects in a specific order. For example, if you have a string "ABC," its permutations would be "ABC," "ACB," "BAC," "BCA," "CBA," and "CAB." Generating all possible permutations of a string is a common problem in computer science and can be approached using various algorithms. In this article, we will explore a Java program that generates all permutations of a given string and explain how it works.
Problem Statement
The problem is to generate and print all possible permutations of a given string.
Example
Let's take the string "ABC" as an example. The expected output for this input should be:
ABC
ACB
BAC
BCA
CBA
CAB
Idea to Solve the Problem
To generate all permutations of a string, we can use a recursive approach. We'll swap characters in the string and recursively generate permutations for the remaining characters. After the recursive call, we will restore the original order of characters to explore other permutations.
Algorithm
-
Define a
swap
function that takes a string and two indices (a and b) as input. This function will swap the characters at indices a and b in the string. -
Define a
findPermutation
function that takes the current string, the current index (n), and the size of the string as inputs. -
In the
findPermutation
function:- If n is greater than the size of the string, return.
- If n is equal to the size of the string, print the current string and return.
- Iterate through the characters of the string from index n to the end:
- Swap the character at index n with the character at the current iteration index.
- Recursively call the
findPermutation
function with the updated string and n+1. - Restore the original order of characters by swapping back the characters at indices n and the current iteration index.
-
In the
main
function:- Create an instance of the
Permutation
class. - Initialize a string (e.g., "ABC") and its size.
- Call the
findPermutation
function with the initial string, index 0, and size. - Repeat the above steps for different strings and sizes.
- Create an instance of the
Pseudocode
class Permutation:
function swap(text, size, a, b):
if (a is within valid bounds) and (b is within valid bounds):
Swap characters at indices a and b in text
return updated text
function findPermutation(text, n, size):
if n > size:
return
if n == size:
Print text
return
for i from n to size:
text = swap(text, size, i, n)
findPermutation(text, n + 1, size)
text = swap(text, size, i, n)
main:
Initialize a Permutation object
Initialize a text (e.g., "ABC") and its size
Call findPermutation with text, 0, and size
Change text and size to new values (e.g., "abcd" and its size)
Call findPermutation with new text, 0, and size
Code Solution
-
1) Print all permutations of a string in java
2) Print all permutations of a string in c++
3) Print all permutations of a string in c
4) Print all permutations of a string in c#
5) Print all permutations of a string in php
6) Print all permutations of a string in python
7) Print all permutations of a string in ruby
8) Print all permutations of a string in scala
9) Print all permutations of a string in swift
10) Print all permutations of a string in kotlin
11) Print all permutations of a string in node js
12) Print all permutations of a string in golang
13) Print all permutations of a string in vb.net
14) Print all permutations of a string in typescript
Time Complexity
The time complexity of this approach is determined by the number of permutations generated. For a string of length N, there are N! (N factorial) permutations. Therefore, the time complexity is O(N!) as the algorithm generates and prints all permutations. This can be an expensive operation for larger strings due to the factorial growth.
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