1
\$\begingroup\$

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));
         }
         
}
\$\endgroup\$
3
  • \$\begingroup\$ "... where I was asked to solve this question" Well, that doesn't involve us here, does it? \$\endgroup\$ Apr 15 '17 at 18:39
  • 1
    \$\begingroup\$ Looks like permute() involves both looping and recursion. At a first glance I'd suggest using one or the other, not both. \$\endgroup\$
    – user132961
    Apr 15 '17 at 18:42
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – Imus
    Apr 15 '17 at 18:58
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.