Java Program to find permutations of the given string. The aim is to find the arrangements of characters in all the ways possible. If the given string has n characters, then n! different arrangements are possible.

Ex:  abc
(All the possible permutations are: abc, acb, bac, bca, cab, cba )

Algorithm to find permutations of String

We need to generate all the possible permutations of the given string using recursion. For that, we will create a function that will swap the first character of the given string with all the other characters recursively until the original string is obtained.

First, we will create a permute function that takes 3 arguments:

•  the given string
•  first index (f)
•  last index (l)

Secondly, we will create a for loop which generates the next possible permutation of the given string. The for loop iterates from index 1 to the last index of the given string and swap each character with the first character of the string.

The for loop will be such that it runs till the original string is obtained so as to avoid duplication.

The function returns when the first index becomes equal to the last index.

Java Program to find permutations of the string

import java.util.Scanner;
public class StringPermutations
{
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int n=s.length();
        permute(s,0,n-1);
    }
    private static String swap(String s, int i, int j) 
    { 
        char temp; 
        char[] c = s.toCharArray(); 
        temp = c[i] ; 
        c[i] = c[j]; 
        c[j] = temp; 
        return String.valueOf(c); 
    } 
    private static void permute(String s, int f, int l) 
    { 
        if (f == l) 
            System.out.println(s); 
        else
        { 
            for (int i = f; i <= l; i++) 
            { 
                s = swap(s,f,i); 
                permute(s, f+1, l); 
                s = swap(s,f,i); 
            } 
        } 
    } 
}

Input:  abc

Output:  abc, acb, bac, bca, cba, cab

Input: ag

Output: ag, ga

Input:  zdsg

Output:  zdsg, zdgs, zgds, zgsd, zsdg, zsgd, dzgs, dzsg, dgsz, dgzs, dsgz, dszg,

sgzd, sgdz, sdgz, sdzg, szdg, szgd, gzds, gzsd, gdsz, gdzsz gsdz, gszd

Input: g

Output:  g