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

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.