轉化這個遞歸進行迭代

我有這樣一段代碼遞歸得到字符串的所有排列在一組：轉化這個遞歸進行迭代

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

轉化這個遞歸進行迭代

回答

相關問題