String Permutation Implemention

Question

The objective is simple: List all possible permutations for a given a String. I looked at some implementations from popular sources. I decided to build this to the flow:

The Code for Review

    package com.progint;

    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.io.BufferedReader;
    import java.io.IOException;
    
    public class StringPermutations {

    public static ArrayList<String> permutations = new ArrayList<String>();
    public static String permutand;

    public static ArrayList<String> permuteString() {
        permutations = permuteString(permutand);
        return permutations;
    }

    public static ArrayList<String> permuteString(String permutand) {
        ArrayList<String>  listOfPermutations = new ArrayList<String>();
        if(permutand.length()==1) {
            listOfPermutations.add(permutand);  
            return listOfPermutations;
        }
        /* Iterate over All character Values */
        for (int i=0; i<permutand.length(); i++) {
            String nextStringPermutation;
            if (i==0) { /* All characters following need to be permuted */
                nextStringPermutation = permutand.substring(i+1);
            }
            else {     /* All characters--not including the current base character-- need to be permuted */
                nextStringPermutation = "".concat(permutand.substring(0,i));
                if(i+1 < permutand.length()) {
                    nextStringPermutation = nextStringPermutation.concat(permutand.substring(i+1));
                }
            }
            /* Retrieve list of possible sub-permutations and build a list with all possibilities */
            ArrayList<String> innerListOfPermutations = permuteString(nextStringPermutation);
            for (String permutation : innerListOfPermutations)
                listOfPermutations.add(permutand.substring(i,i+1).concat(permutation));
        }
        return listOfPermutations;
    }

    public static void main(String[] args) throws IOException {
        ArrayList<String> permutations;
        BufferedReader consoleReader = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the string to permute");
        permutand = consoleReader.readLine();
        permutations = permuteString();
        System.out.println("The " + permutations.size() + " permutations are:");
        for(String permutation : permutations) {
            System.out.println(permutation);
        }
    }
}

I get a 'tarot deck being shuffled' vibe with this implementation.

My Inspirations (for Comparison)

The below is from Programming Interviews Exposed:

void permute(String str){
    int length = str.length();
    boolean[] used = new boolean[length];
    StringBuffer out = new StringBuffer();
    char[] in = str.toCharArray();
    doPermute(in, out, used, length, 0);
}
void doPermute(char[] in, StringBuffer out, boolean[] used, int length, int level) {
    if( level == length ){
        System.out.println( out.toString() );
        return;
    }
    for(int i = 0; i < length; ++i ){
        if(used[i]) continue;
        out.append(in[i]);
        used[i] = true;
        doPermute( in, out, used, length, level + 1 );
        used[i] = false;
        out.setLength(out.length()-1);
    }
}

I also looked at this very concise implementation based on swapping.

Answer 1

The sources of inspiration aren't really up for review, but they have a couple of things in common:

• They print the permutations, instead of storing them in a list. They could be adapted though.
• They recurse on a smaller string, but they do not create a physical string object with the new length. Characters are "removed" from the string not by physically removing them, but by changing bounds (the C++ implementation) or by marking them as "used" (PIE). Either way they manage to avoid doing a bunch of string processing.

But let's look at what you wrote, of course.

Passing values into functions via static variables, which permuteString() relies on, is a bad practice. permuteString(String permutand) is what I would have recommended as a replacement, you can call it directly from main and remove permuteString().

Since you pass a physically shorter string down to the next level of recursion, on the way back up you need to prepend a character to all the results of the recursive call. It would be less awkward (and cost less string manipulation) to pass down a prefix which would be prepended before putting a string in the list.

Note that both of your sources of inspiration effectively do that, but in a way that also avoids the need to actively prepend the prefix, since it is already there. The C++ implementation passes that prefix in the part of the array that is implicitly treated as such, the PIE implementation passes the prefix in the buffer out.

The strings would end up in the list in their final form, with no further processing needed. That makes it simple to use a different strategy for the list: you can also pass it down, rather creating lots of new lists and copying the contents of one into the other all the time. That would result in a slightly annoying-to-use void permuteString(String permutand, ArrayList<String> results) rather than a ArrayList<String> permuteString(String permutand), but you could easily implement the latter as a simple wrapper around the first (the awkward form would become only an implementation detail).

This logic to remove one character from the string,

String nextStringPermutation;
if (i==0) { /* All characters following need to be permuted */
    nextStringPermutation = permutand.substring(i+1);
}
else {     /* All characters--not including the current base character-- need to be permuted */
    nextStringPermutation = "".concat(permutand.substring(0,i));
    if(i+1 < permutand.length()) {
        nextStringPermutation = nextStringPermutation.concat(permutand.substring(i+1));
    }
}

Could be simplified substantially by using a StringBuilder, which offers the method deleteCharAt(int index).

But I would recommend not doing that either, and instead following one of your sources of inspiration more closely, so that there is no need for such string manipulations. Doing it in a simpler way is still not as simple as not doing it at all.