current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 3 down vote favorite

This generates all possible permutations of the string. I am also unable to understand the time complexity of this problem. Can someone please explain the complexity to me?

import java.util.ArrayList;


public class permutations {

    public ArrayList<String> performPermutations(String s){
        ArrayList<String> arrayList = new ArrayList<String>();
        if (s == null) {
            return null;
        }

        else if (s.length() == 0) {
            arrayList.add("");
            return arrayList;
        }

        else {
            for (int i = 0; i < s.length(); i++) {
                ArrayList<String> remaining = performPermutations(s.substring(0, i) + s.substring(i + 1));
                for (int j = 0; j < remaining.size(); j++) {
                    arrayList.add(s.charAt(i) + remaining.get(j));
                }
            }
            return arrayList;
        }
    }


    public static void main(String[] args) {
        permutations p = new permutations();
        ArrayList<String> arr = p.performPermutations("abcde");
            for(int i = 0; i<arr.size();i++) {
                System.out.println(arr.get(i));
            }
        }
    }
}
share|improve this question
5  
We can review your code (if it all works), but not explain the complexity, as we do not assist in explaining code given in the question. – Jamal♦ Sep 18 '14 at 4:10
1  
Welcome to Code Review, Add an expected input/output along with some more explanation of exactly what your code does. See stackoverflow.com/questions/487258/… – JaDogg Sep 18 '14 at 7:34
up vote 2 down vote accepted

There are quite a few ways this code can be improved:

  • All class names should start with a capital, and be in CamelCase. Specifically, the class permutations should be Permutations. The way it doesn't look like a variable, as in here:

    permutations p = new permutations();

performPermutations method

  • Why does it declare a return type of ArrayList<String>? Is there anything special about the implementation of the list? It should just be List<String>.

  • You have an unnecessary if-else structure, since each if statement returns a value. You can remove all of the elses.

  • In the first if statement, you return null. This is a bad idea in many cases. An empty list would be more favorable, just in case any calling code wants to operate on it immediately afterwards. (Notice that your main method would fail with a NullPointerException if the passed in list was empty).

  • You can combine the first and second if statements into one. This would be your "base" case:

    if (s == null || s.isEmpty() { return arrayList; }

    Never compare a list length to 0, use isEmpty() instead. Also, s is a poor name for a method parameter. Try to be creative and descriptive. Finally, there's no need to add an empty string if the list is empty.

  • There's a lot of existing posts on string permutations you may find interesting. Seeing a recursive call embedded in two for loops is probably unnecessarily complex.

How this method could look (but can still be improved):

public List<String> performPermutations(final String s){

    final List<String> result = new ArrayList<String>();

    if (s == null) {
        return result;
    }

    for (int i = 0; i < s.length(); i++) {
        final List<String> remaining = performPermutations(s.substring(0, i) + s.substring(i + 1));
        for (int j = 0; j < remaining.size(); j++) {
            result.add(s.charAt(i) + remaining.get(j));
        }
    }

    return result;
}
share|improve this answer
    
I believe there's a bug at the if (s == null || s.isEmpty()). By removing the result.add(""), you're returning an empty list up to the parent recursive steps, which will ultimately cause an empty list to be returned overall. – Rahin May 31 '15 at 3:05
    
@Rahin thanks for the sharp eye! – lealand May 31 '15 at 3:18
    
Hmm maybe the page isn't refreshing correctly, but I don't think making the string and the list "final" and removing the isEmpty condition would fix the issue – Rahin May 31 '15 at 3:25
    
Please feel free to edit or post a new answer which I'll upvote. It's too late for me to reexamine this answer. – lealand May 31 '15 at 3:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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