Posted on by Kalkicode
Code Backtracking

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

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.

New Comment