# 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

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

2. Define a `findPermutation` function that takes the current string, the current index (n), and the size of the string as inputs.

3. 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.
4. 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.

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

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

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