Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Write a method to compute all permutations of a string

Sharing is caring!

Problem Statement
Write a method to compute all permutations of a string

Solution
Let’s assume a given string S represented by the letters A_1, A_2, A_3,\dots, A_n

To permute set S, we can select the first character, A_1, permute the remainder of the string to get a new list Then, with that new list, we can “push” A_1 into each possible position.

For example, if our string is “abc”, we would do the following:
1 Let first = “a” and let remainder = “bc”
2 Let list = permute(bc) = {“bc”, “cd”}
3 Push “a” into each location of “bc” (–> “abc”, “bac”, “bca”) and “cb” (–> “acb”, “cab”, “cba”)
4 Return our new list

Code

public class Permutations {
    static String insertCharAt(String str, char c, int index) {
        StringBuffer sb = new StringBuffer(str.substring(0, index));
        sb.append(c);
        sb.append(str.substring(index));
        return sb.toString();
    }

    static List<String> permutations(String s) {
        List<String> ans = new ArrayList<String>();
        if (s.length() == 0) {
            ans.add("");
            return ans;
        } else {
            char first = s.charAt(0);
            List<String> words = permutations(s.substring(1));
            for (String word : words) {
                for (int i = 0; i <= word.length(); i++) {
                    ans.add(insertCharAt(word, first, i));
                }
            }

            return ans;
        }
    }

    public static void main(String[] args) {
        System.out.println(permutations("abc"));
    }
}