java - 将这种递归转换为迭代

Question

我有这段代码，可以递归地获取集合中字符串的所有排列:

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;
    }
}

如果我的数组列表包含太多值，它就会溢出堆栈。我后来了解到，将算法从递归转换为迭代将帮助我解决这个内存问题，因为我将自己在堆上处理堆栈而不是使用 native 堆栈。我以前从未这样做过，也不知道如何解决这个问题。我的问题并不像这种转变的例子那么简单，因此我将非常感谢有关我如何实现这一目标的一些提示。

Answer 1

像下面这样使用特殊的 WorkPair 类来模拟将在递归方法中创建的堆栈帧怎么样？通常，当转换为迭代方法时，您可能需要创建一个存储部分工作的数据结构，因为在递归方法中，此信息存储在堆栈中(我们没有)。

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;
}