Java recursion to find all the possible permutations & combinations in Arraylist quits too early

Question

I'm writing a recursive permutations program in Java to find all the possible permutation of the Strings in an Arraylist. I know there are a lot of posts similar to this, but I haven't found one that addresses this issue specifically.

The problem I have with my code is that it only runs the first permutation and then quits

I know that it's doing this because every time it is called, an item is removed but the indexes shift so its only doing one call per element, but I don't know how to fix it. I've tried changing the for-loop conditions, removing the element at different spots, adding base cases, but everything seems to only make it worse. As it is now, the input[w,h,a,t]would return an arrayList with elements [what,hat,at,t]. The expected output is all the permutations of the four letters.

Where do I go from here? I know I'm close but I've been stuck on this for several days

Any help would be greatly appreciated

public class wordFinder {
    static ArrayList<String> permutations = new ArrayList<String>();
    public static String findPermutations(ArrayList<String> letterArray) {
        String prefix = "";
        for (int i = 0; i < letterArray.size(); i++) {
            String temp = letterArray.remove(i);
            prefix = temp + findPermutations(letterArray);
            permutations.add(prefix);
        }
        return prefix;
    }
}

first check whether you really wanna use for loops if you want a recursion — Thusitha Thilina Dayaratne, Sep 26 '14 at 02:57
@shinjw yes, there _is_ a recursive call. @azurefrog a recursive function can have a `for` loop, there's nothing inherently wrong with that — Óscar López, Sep 26 '14 at 02:58
@ÓscarLópez It is true that there is nothing inherently wrong with that in general, but in this case the OP is both modifying `letterArray` on each time through the loop, and also passing the same reference down to be emptied in the recursive call. The second time through the outermost for-loop will (I expect) have an empty `letterArray`, and fall through the `i < letterArrays.size()` check. Since the for-loop as written will always only execute once, I question the logic in having it. — azurefrog, Sep 26 '14 at 03:02
azurefrog is right, after the recursive call, `letterArray` is empty. The reason for the for-loop is to append `prefix` to the recursive call for every element, but that's not happening because the indexes shift — user2913576, Sep 26 '14 at 03:06
Check your logic. You recursion happens over and over and over before permutations.add(prefix) is ever reached — shinjw, Sep 26 '14 at 03:11
There's a good explanation of finding all permutations of a string [here](http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string), the answers there should give you some ideas on how to write a recursive method like you are trying to. You could use one of the solutions there, and write an outer method which calls the recursive method, giving it a succession of shorter and shorter substrings, until you've gotten all permutations of all lengths. — azurefrog, Sep 26 '14 at 03:13
@Infinite Recursion expected output is all the permutations of the four letters — user2913576, Sep 26 '14 at 03:45

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

Note: Using ArrayLists like this for alphabets, along with for-loop and recursion is not optimal and extremely expensive in term of resources. This solution is only to illustrate the concept of recursion as mentioned in the question.

As you are looking for the recursive solution, to understand the concept, here it is.

The primary idea is that as you keep removing an alphabet from the ArrayList, keep adding them to another list so that they don't get lost and use both the lists to find all the possible combinations.

Code:

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

public static void main(String[] args) {
    ArrayList<String> letterArray = new ArrayList<String>();
    letterArray.add("w");
    letterArray.add("h");
    letterArray.add("a");
    letterArray.add("t");
    wordFinder(new ArrayList<String>(), letterArray);
    System.out.println(Arrays.asList(permutations));
}

public static void wordFinder(ArrayList<String> sub,
        ArrayList<String> letterArray) {
    permutations.add(sub.toString());
    if (letterArray.size() != 0) {
        for (int i = 0; i < letterArray.size(); i++) {
            ArrayList<String> prefix = new ArrayList<String>(sub);
            prefix.add(letterArray.get(i));
            ArrayList<String> postfix = new ArrayList<String>(letterArray);
            postfix.remove(i);
            wordFinder(prefix, postfix);
        }
    }
}

Thank you! I never thought to split the original array into pre- and post- arrays, I just kept trying to create a temp and modify the original one. This is a lot neater — user2913576, Sep 26 '14 at 04:53

score 0 · Answer 2 · answered Sep 26 '14 at 04:02

You dont need a recursion for that.

You can do this by simple iterations: Try:

public class wordFinder {
    public static ArrayList<String> findPermutations(ArrayList<String> letterArray) {
        ArrayList<String> result = new ArrayList<String>();
        for (int i = 0; i < letterArray.size(); i++) {
            String current = letterArray.get(i);
            for (int j = i +1; j < letterArray.size(); j++) {
                current = current + letterArray.get(j); 
            }
            result.add(current);

        }
        return result;
    }
}

This will return an array of Strings just how you expect!

Hope it helps!

Thanks, but I'm looking for the recursive solution. Its not so much the conceptualization, but the implementation that I don't understand — user2913576, Sep 26 '14 at 04:13

Mr37037 · Answer 3 · 2014-09-26T04:59:38.057

You should say thanks to @Cesar Villasana. Because i just converted hi solution to recursive one. Here is this code and you will get your desired output.

public class Test {

         /*static int i=0;
         static ArrayList<String> result = new ArrayList<String>();
         public static void findPermutations(ArrayList<String> letterArray) {

             //int i=0;
             if(i>=letterArray.size()){
                 return;

             }else{

                 String current = letterArray.get(i);
                 for (int j = i +1; j < letterArray.size(); j++) {
                     current = current + letterArray.get(j); 
                 }
                 result.add(current);

             i++;
             findPermutations(letterArray);
         }

         }*/
        public ArrayList<ArrayList<String>> generatePerm(ArrayList<String> original) {
            if (original.size() == 0) { 
              ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
              result.add(new ArrayList<String>());
              return result;
            }
            String firstElement = original.remove(0);
            ArrayList<ArrayList<String>> returnValue = new ArrayList<ArrayList<String>>();
            ArrayList<ArrayList<String>> permutations = generatePerm(original);
            for (ArrayList<String> smallerPermutated : permutations) {
              for (int index=0; index <= smallerPermutated.size(); index++) {
                ArrayList<String> temp = new ArrayList<String>(smallerPermutated);
                temp.add(index, firstElement);
                returnValue.add(temp);
              }
            }
            return returnValue;
          }
    public static void main(String[] args){
        ArrayList<String > b=new ArrayList<String>();
        b.add("w");
        b.add("h");
        b.add("a");
        b.add("t");
    Test t=new Test();
//  t.findPermutations(b);
    //  System.out.println(t.result);
    System.out.println(t.generatePerm(b));
    }

}

This still only gives me the original ArrayList with one element subtracted each time, output should be n! permutations of all the letters — user2913576, Sep 26 '14 at 04:42

Java recursion to find all the possible permutations & combinations in Arraylist quits too early

3 Answers3

Code: