Transforming this recursion to iteration

Question

I have this piece of code that recursively gets all permutations of Strings in a set:

public static List<List<String>> combinations(List<String> strings)
{
    if (strings.size() > 1)
    {
        List<List<String>> result = new ArrayList<List<String>>();

        for (String str : strings)
        {
            List<String> subStrings = new ArrayList<String>(strings);
            subStrings.remove(str);

            result.add(new ArrayList<String>(Arrays.asList(str)));

            for (List<String> combos : combinations(subStrings))
            {
                combos.add(str);
                result.add(combos);
            }
        }

        return result;
    }
    else
    {
        List<List<String>> result = new ArrayList<List<String>>();
        result.add(new ArrayList<String>(strings));
        return result;
    }
}

If my arraylist holds too many values, it overflows the stack. I have since learned that transforming the algorithm from recursion to iterative would help me solve this memory issue since I would be handling the stack myself on the heap rather than using the native stack. I have never done this before and cannot wrap my head around how to do that with this problem. My problem is not as simple as the examples of seen of this transformation, so some hints as to the how I could achieve this would be much appreciated.

I suggest that you back up and try to describe *in words* the steps in an iterative algorithm to solve the same problem. If you are unable to do this immediately, then back up another step and work through an example. — Code-Apprentice, Jun 11 '13 at 23:30
i don't recommend you call a variable combinations like the method :S is difficult to understand — nachokk, Jun 12 '13 at 00:27
Another way to save memory is to not produce all the combinations at once in a list, but use a "generator" function that produces a single combination each time it's called. — Lee Daniel Crocker, Jun 12 '13 at 14:27

selig · Accepted Answer · 2013-06-12T14:21:27.820

How about something like the following which uses a special WorkPair class to emulate the stack frames that would be created in the recursive approach. Generally when converting to an iterative method you may need to create a data structure that stores partial working as in a recursive approach this information is stored on the stack (which we don't have).

private static class WorkPair{

  public final List<String> so_far;
  public final List<String> left;
  public WorkPair(List<String> sf,List<String> l){
    so_far=sf;left=l;
  }

}

public static List<List<String>> combinationsIterative(List<String> strings)
{

    Queue<WorkPair> queue = new LinkedList<WorkPair>();

        // setup queue
        for(String str : strings){
           List<String> so_far = new ArrayList<String>(Arrays.asList(str));
           List<String> left = new ArrayList<String>(strings);
           left.remove(str);
           queue.add(new WorkPair(so_far,left));
        }

        // collect the results
        List<List<String>> result = new ArrayList<List<String>>();            
        while(!queue.isEmpty()){
          WorkPair pair = queue.remove();
          // at each stage add the list so_far
          List<String> so_far_add = new ArrayList<String>(pair.so_far);
          result.add(so_far_add);

          // if there's more work to be done create more workpairs
          if(pair.left.size()>0){
            // push work items for so_far + one element of left
            for(String str : pair.left){
                   List<String> so_far = new ArrayList<String>(pair.so_far);
                   so_far.add(str);
                   List<String> left = new ArrayList<String>(pair.left);
                   left.remove(str);
                   queue.add(new WorkPair(so_far,left));      
            }
          }

        }

    return result;
}

score 1 · Answer 2 · edited May 23 '17 at 10:25

What you basically need is an iterative powerset construction. Have a look at this sample code (section 'Iterative') to see how to accomplish the task for collections in Java. If you need to distinguish between different orders when combining a given subset of your original strings you would have to generate all permutations of each powerset element in a second processing step. This page will get you started on how to achieve it (using the code provides you with all permutations of the indexes 1..<list_size>, add a trivial mapping to get the ordered string lists).

Consider however whether or not you really need an explicit representation of the string sets. You may equivalently employ the numbers k in 1..<original set size> taken as bit vectors with bit #i indicating whether or not the string at position iin your source list is contained. in the case of ordered combinations, the permutations will be uniquely determined by k and its number of 1 bits.

As permutations are sortable, you actually need only 2 numbers + your original list to uniquely identify each element of your result and to easily reconstruct the actual string combination.

This SO question might also be of interest to you.

Transforming this recursion to iteration

2 Answers2