Print all permutations of a given string

Posted by N.K. Chauhan on Mar 31, 2024

A string s is given, the task is to print all the permutations of s using recursion.

A string of length n has n! permutation.

Example 1: Print all permutations of "abc".

Input: "abc"
Output:

abc
acb
bac
bca
cba
cab

Example 2: Print all permutations of "xyzd".

Input: "xyzd"
Output:

xyzd
xydz
xzyd
xzdy
xdzy
xdyz
yxzd
yxdz
yzxd
yzdx
ydzx
ydxz
zyxd
zydx
zxyd
zxdy
zdxy
zdyx
dyzx
dyxz
dzyx
dzxy
dxzy
dxyz


Solutions

Method 1: Recursion & Swapping

In this solution we can get all the permutations using recursion while swapping character at index with all the character after it in the string.

Once the string is completely traversed (index at last element) we print the swapped string - base condition.

package com.cb.recursion;
/*
 * Recursion + Swapping
 * */
public class R12_PermutationsOfString {

    public static void printPermutations(String s, int index) {

        // print if index is at last element
        // no more element to the right for swapping
        if (index >= s.length() - 1) {
            System.out.println(s);
            return;
        }

        // swap with self and elements after current index
        for (int i = index; i < s.length(); i++) {
            printPermutations(swap(s, index, i), index + 1);
        }
    }

    private static String swap(String s, int i, int j) {

        char[] chars = s.toCharArray();

        char c = chars[i];
        chars[i] = chars[j];
        chars[j] = c;

        return new String(chars);
    }

    public static void main(String[] args) {
        printPermutations("abc", 0);
    }
}
abc
acb
bac
bca
cba
cab

Complexity

There are n! permutations and it requires O(n) time to print a permutation so Time Complexity is O(n*n!).

Related


Swap all occurrences of two characters to get lexicographically smallest string

Reverse words in a given string

Transform One String to Another with a Minimum Number of Operations

Check if two strings are equal or not after processing backspace

Print all subsequences of a string

Power Set: Print all non-empty subsequences of a string

Check whether the given string is a palindrome

Longest Common Prefix in an Array of Strings

Check if two given strings are isomorphic to each other

Find all substrings of a string in "O (n^2)" time