Permutations of a string

Today I had an interview, where I was asked to solve this question:

Find all the permutations of a given string

Example: str = 'abc'

Answer: 'abc', 'acb', 'bac', 'bca', 'cab', 'cba'

I have written this code, but can it be improved or is there any other way to do it in better manner?

public class Permutation{
public static void main(String []args){
Permutation p = new Permutation();
String str = "1234";
int n = str.length();
p.permute(str, 0 ,n-1);

}

public static void permute(String str, int l, int r){
if(l==r){
System.out.println(str);
}

for(int i=l;i<=r;i++){
str = swap(str,i,l);
permute(str, l+1, r);
str = swap(str,i,l);
}
}

public static String swap(String str, int i, int l){
char[] charArr = str.toCharArray();
char t = charArr[i];
charArr[i] = charArr[l];
charArr[l] = t;
return (String.valueOf(charArr));
}

}
• "... where I was asked to solve this question" Well, that doesn't involve us here, does it? Apr 15, 2017 at 18:39
• Looks like permute() involves both looping and recursion. At a first glance I'd suggest using one or the other, not both.
– user132961
Apr 15, 2017 at 18:42
• The rules on this site state that the code you put up for review should be your own. Instead of just posting the question to see how we would solve it, you should at least add your own attempts to improve it and then ask us if there are some other things that you missed.
– Imus
Apr 15, 2017 at 18:58

Calling static methods

public class Permutation{

Permutation doesn't really fit. This isn't a permutation. It's something that creates permutations. Consider names like Permuter or PermutationUtils.

Permutation p = new Permutation();
String str = "1234";
int n = str.length();
p.permute(str, 0 ,n-1);

}

public static void permute(String str, int l, int r){

You don't need to call static methods from an object. This could be just

String str = "1234";
int n = str.length();
Permutation.permute(str, 0, n - 1);
}

public static void permute(String str, int l, int r) {

There's no need to instantiate an object.

Beyond that, I'd actually prefer

PermutationUtils.permute("1234");
}

public static void permute(String str) {
permute(str, 0, str.length() - 1);
}

private static void permute(String str, int l, int r) {

The caller shouldn't have to know details about how the method is called in my opinion.

Instantiating and using an object

class Permuter {

private final String original;
private final List<String> permutations = new ArrayList<>();

public Permuter(String original) {
this.original = original;
}

public List<String> permute() {
if (permutations.empty()) {
permute(original, 0, original.length() - 1);
}

return permutations;
}

That's an example of how the class could be defined if it was meant to be instantiated. Then you could call it like

public static void main(String[] args) {
Permuter p = new Permuter("1234");
for (String permutation : p.permute()) {
System.out.println(permutation);
}
}

This also returns the permutations and only displays them in the main method. This is generally a better practice. This way if what they really wanted was the permutations, you don't have to rewrite the whole code to give it to them.

You may want to consider using a longer variable name than p. It's OK here, as it's only used on adjacent lines. But in a longer method, single letter variables names can get confusing.

Don't do unnecessary work

for(int i=l;i<=r;i++){
str = swap(str,i,l);
permute(str, l+1, r);
str = swap(str,i,l);
}

This pattern is what you would use if str were a mutable, like a StringBuilder or array. Since swap creates a new string, you could just say

for (int i = l; i <= r; i++) {
permute(swap(str, i, l), l + 1, r);
}

It's not necessary to call swap twice, since it doesn't change the original string. This way str never changes.

I also changed the spacing. It's easier to see where the variables start and end if there are spaces around the operators.

If efficiency matters

If efficiency matters, consider using a mutable instead. This version creates a new string every time swap is called. With a mutable, it could create a new string only when it needed to add to the list or display.