Variable Number of Nested For Loops

Question

I'm making a word unscrambler in java. Right now I have a program that can print all rearrangements of 3 letters chosen from a word with 3 or more letters (no repeats). So for example, if the parameter is abcd, it will print this:

[[abc, abd, acb, acd, adb, adc, bac, bad, bca, bcd, bda, bdc, cab, cad, cba, cbd, cda, cdb, dab, dac, dba, dbc, dca, dcb]]

I'm filling a 2D array list with the permutations. Right now the 2D array has only one array inside of it, which contains the permutations for 3 letters. I want the 2D array to have arrays for permuations of 1 letter, 2 letters, 3 letters, and so on, stopping at the length of the word. The problem is that I need a variable number of nested for loops to accomplish this. For the 3 letter permutations, I have 3 nested for loops. Each one cycles through the letters in the parameter.

public static void printAllPermuations(String word)
{
    int len = word.length();
    ArrayList<String> lets = new ArrayList<String>();
    //this array of letters allows for easier access
    //so I don't have to keep substringing
    for (int i = 0; i < len; i++)
    {
        lets.add(word.substring(i, i + 1));
    }

    ArrayList<ArrayList<String>> newWords = new ArrayList<ArrayList<String>>();
    newWords.add(new ArrayList<String>());
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len; j++)
        {
            for (int k = 0; k < len; k++)
            {
                if (i != j && i != k && j != k)
                //prevents repeats by making sure all indices are different
                {
                    newWords.get(0).add(lets.get(i) + lets.get(j) + lets.get(k));
                }
            }
        }
    }
    System.out.println(newWords);
}

I've looked at other posts and I've heard that recursion can solve this. I don't know how I would implement that, though. And I've also seen some complicated solutions that I don't understand. I'm asking for the simplest solution possible, whether it involves recursion or not.

Answer 1

Based on what @DrYap said, I wrote this (it's a little different than his):

Here is the code to start it off:

for(int i = 1; i <= len; i++)
{
    newWords.add(new ArrayList<String>());
    loop(i);
}

Here is the loop method. A lot of the variables were declared as instance variables so I don't have to pass them into the parameter:

public static void loop(int level)
{
    if (level == 0)
    {
        int pos = indices.size() - 1;
        int pos2 = newWords.get(pos).size();
        newWords.get(pos).add("");
        for (Integer letIndex : indices)
        {
            String previous = newWords.get(pos).get(pos2);
            newWords.get(pos).set(pos2, previous + lets.get(letIndex));
        }
    }
    else
    {
        for (int i = 0; i < len; i++)
        {
            if (!indices.contains(i))
            {
                int indicesIndex = indices.size();

                indices.add((Integer) i);
                loop(level - 1);
                indices.remove(indicesIndex);
            }
        }
    }
}

Answer 2

I will not give you the actual code, but this should give you the idea how the recursion can look like (I believe there are other way to do it recursively :P )

void findAllCombination(String tmpResult, 
                        String rawString, 
                        int noOfChar, 
                        List<String> allCombinations) {
  if (tmpResult.size() == noOfChar) {
    allCombinations.add(tmpResult );
  } else {
    for (i in 0 to rawString.size()) {
      findAllCombination(tmpResult + rawString[i], 
                         rawString.removeCharAt(i),
                         noOfChar, 
                         allCombinations);
    }
  }
}

List<String> foo(String input, int level) {
    List<String> allResults = ...;
    findAllCombination("", input, level, allResults);
    return allResults;
}

The main recursion part is the findAllCombination. The idea is strict forward. For way to find all permutation is, for the rawString input that we have, we take out the character one by one, and append to the previously found tmpResult, and use that tmpResult to do further processing. Once we hit the point that the tmpResult is long enough, then we put the tmpResult to the result allCombinations list.

(foo() method is here just to make your invocation easier :P Codes that actually do the works is only 6 lines, excluding lines with only brackets and ignoring lines that I break intentionally for better readability )

Answer 3

With the recursive method you would put one of your looping in a function pass the loop parameters to that function. Then from within the function's loop, it calls its to nest another loop.

void loopFunction(ArrayList<ArrayList<String>> newWords, int level) {
    if (level == 0) { // terminating condition
        if (/* compare the indices by for example passing down a list with them in  */)
        {
            newWords.get(...).add(...);
        }
    } else {// inductive condition
        for (int i = 0; i < len; i++) {
            loopFunction(newWords, level-1);
        }
    }
}

So for your example you need 3 levels of recursion so you would start the recursion with:

loopFunction(newWords, 3);

Edit

Since you have been having trouble here is a working version. It keeps a list of indices to compare against and it builds up the string as it goes. The rearranged words are added to the 2D array at each level to get all lengths of words. With recursion it is easiest to think functionally and not change and keep the variables immutable (unchangeable). This code mostly does that although I update the indices rather than create a new copy for convenience.

void loopFunction(ArrayList<String> lets, ArrayList<ArrayList<String>> newWords, int level, ArrayList<Integer> indices, String word) {
    if (level == 0) { // terminating condition
        return;
    } else { // inductive condition
        for (int i = 0; i < lets.size(); i++) {
            if (!indices.contains(i)) { // Make sure no index is equal
                int nextLevel = level-1;
                String nextWord = word+lets.get(i);

                newWords.get(level-1).add(nextWord);

                indices.add(i);
                loopFunction(lets, newWords, nextLevel, indices, nextWord);
                indices.remove((Integer) i);
            }
        }
    }
}