Swapstr – Java Program to Find String Permutation Using Recursion

by

Swapstr: In this article we are going to see how we can find string permutation using recursion by Java programming language.

Java Program to Find String Permutation Using Recursion

Recursive string permutation: A string permutation refers to the number of different string can be formed from a single string.

For example:

A string is 'ab'
So its string permutation: 'ab' and 'ba'

Let’s see the program to understand it clearly.

 

Method-1: Java Program to Find String Permutation Using Recursion By Using Static Input Value

Approach:

  • Store the string first.
  • Call the user defined method strPermute( ) on the string.
  • The user defined method creates a character array and iterates through all the elements in the string and then prints all its permutations by using another user defined method stringSwap( ) that swaps the characters.

Program:

import java.util.*;
// Main class
public class Main
{
    // Method to swap the string characters
    public static String stringSwap(String s, int i, int j)
    {
        // Storing the string in a character array
        char[] str = s.toCharArray();
        // Swapping the characters at adjacent locations
        char c = str[i];
        str[i] = str[j];
        str[j] = c;
        // Converting the character array back to a string and returning the new string
        String newStr = new String(str);
        return newStr;
    }
    
    // Method to permute the strings
    public static void strPermute(String s,int beg, int end)
    {
        if(beg==end)
        {
            System.out.println(s);
            return;
        }
        for(int i = beg; i <= end ; i++)
        {
            // First we swap the strings to fix the letters of the index at beg
            String swapStr = stringSwap(s, beg, i);
             //calling recursion for the next characters
            strPermute(swapStr, beg + 1, end);
            stringSwap(swapStr, beg, i);
        }
    }

    public static void main(String[] args)
    {
        // String and its length
        String arr = "xyz";
        int length = arr.length();
        System.out.println("The permutations of the string xyz are");
        // Calling the function on our string
        strPermute(arr,0,length-1);
    }
}

Output:

The permutations of the string xyz are
xyz
xzy
yxz
yzx
zyx
zxy

Method-2: Java Program to Find String Permutation Using Recursion By Using User Input Value

Approach:

  • Ask the user to enter the string to generate permutations.
  • Call the user defined method strPermute( ) on the string.
  • The user defined method creates a character array and iterates through all the elements in the string and then prints all its permutations by using another user defined method stringSwap( ) that swaps the characters.

Program:

import java.util.*;
// Main class
public class Main
{
    // Method to swap the string characters
    public static String stringSwap(String s, int i, int j)
    {
        // Storing the string in a character array
        char[] str = s.toCharArray();
        // Swapping the characters at adjacent locations
        char c = str[i];
        str[i] = str[j];
        str[j] = c;
        // Converting the character array back to a string and returning the new string
        String newStr = new String(str);
        return newStr;
    }
    
    // Method to permute the strings
    public static void strPermute(String s,int beg, int end)
    {
        if(beg==end)
        {
            System.out.println(s);
            return;
        }
        for(int i = beg; i <= end ; i++)
        {
            // First we swap the strings to fix the letters of the index at beg
            String swapStr = stringSwap(s, beg, i);
             //calling recursion for the next characters
            strPermute(swapStr, beg + 1, end);
            stringSwap(swapStr, beg, i);
        }
    }

    public static void main(String[] args)
    {
        // Taking user input
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the string to permute ");
        // Storing the string entered by the user
        String arr = sc.nextLine();
        int length = arr.length();
        System.out.println("The permutations of the string "+ arr + " are");
        // Calling the function on our string
        strPermute(arr,0,length-1);
    }
}

Output:

Enter the string to permute 1234
The permutations of the string 1234 are
1234
1243
1324
1342
1432
1423
2134
2143
2314
2341
2431
2413
3214
3241
3124
3142
3412
3421
4231
4213
4321
4312
4132
4123

Practice Java programming from home without using any fancy software just by tapping on this Simple Java Programs for Beginners tutorial.