转化这个递归进行迭代

我有这样一段代码递归得到字符串的所有排列在一组：转化这个递归进行迭代

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

如果我的ArrayList中拥有太多的价值，它溢出堆栈。我从那以后就知道将算法从递归转换为迭代将帮助我解决这个内存问题，因为我将在堆上自己处理堆栈，而不是使用本地堆栈。我从来没有这样做过，也无法将我的头围绕如何解决这个问题。我的问题并不像看到这种转变的例子那么简单，所以我非常赞赏一些关于如何实现这一点的提示。

来源

2013-06-11 sunrize920

我建议你备份并尝试在词语中描述*以迭代算法中的步骤来解决相同的问题。如果您无法立即做到这一点，那么请备份另一个步骤，并通过示例进行操作。 –

我不建议您调用类似于以下方法的变量组合：S很难理解 – nachokk

固定对于您 – sunrize920

如何使用特殊的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; 
}

来源

2013-06-12 10:24:45 selig

你基本上需要的是一个迭代powerset构造。看看this sample code (section 'Iterative')看看如何完成Java中的集合任务。如果在组合给定子集的原始字符串时需要区分不同的顺序，则必须在第二个处理步骤中生成每个powerset元素的所有排列。 This page会让你开始如何实现它（使用代码为您提供索引1..<list_size>的所有排列，添加一个简单的映射来获取有序的字符串列表）。

不管你是否真的需要显式表示字符串集。您可以等同地使用位于1..<original set size>的k中的位作为位向量，位＃i指示是否包含源列表中位置为i的字符串。在有序组合的情况下，置换将由k及其1位的唯一确定。

由于排列是可排序的，您实际上只需要2个数字+您的原始列表来唯一标识结果的每个元素，并轻松重构实际的字符串组合。

This SO question也可能是你感兴趣的。

来源

2013-06-12 10:36:05 collapsar

转化这个递归进行迭代

回答

相关问题