從以下樹型數據結構中獲取所有可能的組合

Question

在下面的內容中，您將看到一個數據結構，它與特徵模型的簡化版本非常相似（對於它們來看看here），並且是某種版本的樹。我已經在Java中實現了數據結構，現在我正在嘗試分析它。具體而言，我想獲得所有可能的元素組合，如果給出了特定的特徵模型。

假設我們有以下特徵模型：

的元素是盒子。未填充的圓圈代表可選元素（請記住o代表可選），填充代表必填。根元素必須包含在內。由於這些規則的元素的以下組合或列表是可能的：

• [1,3,5,6]
• [1,2,3,5,6]
• [1,3 ，4,5,6,7]
• [1,2,3,4,5,6,7]

現在，我想他們不會通過視覺搜索，而是通過一個Java程序。爲此，我實施了幾個類：

• Tree存儲整個特徵模型（圖形）。
• Element是其中一個矩形。
• Edge描述線條和圓圈。
• Combination擁有一種可能的組合（列表組合）。

內Element類，我實現了一個函數來獲取所有組合被稱爲recursiveConfiguration：

public List<Combination> recursiveCombination(List<Combination> combinations){ 

    for(Combination c: combinations){ 
     c.add(this); 
    } 

    // Iterate through all edges of the current element 
    for(Edge e: getEdges()){ 

     int type = e.getType();   

     // In this case getChildren always returns only one feature. 
     Element child = e.getChildren().get(0);    
     List<Combination> childCombinations = child.recursiveCombination(combinations); 

     if(type == 1){ 
      // If type is mandatory 
      combinations = childCombinations; // Line with compiler error 
     }else{ 
      // If type is optional 
      combinations.addAll(childCombinations); 
     }  
    } 
    return combinations; 
} 

算法的說明： 這就是所謂的一個元素的組合的名單，這是一個空的清單。該函數在根元素1上調用。它添加了第一個for循環1的組合（它使用DFS通過樹）。其次，該方法調用自身從元素2開始，傳遞原始列表（包含1）。從那裏返回包含元素1和2的配置。返回的列表根據邊的類型（必需或可選，並相應添加到原始列表）處理。在該特定情況下，該清單應該由兩個組合1和1,2組成。當第一個邊緣下的子樹（在這種情況下，只有元素2）完成時，將處理下一個子樹（3,5,6）。

以下內容不再重要，請在單槓下查看。

但目前我對遞歸感到困惑，因爲當我打電話給這個返回的列表combinations是空的。我相信這與治療葉子的方式有關。因爲目前這些處理不當（參見上面的粗體文字）。 有人有想法嗎？當然，如果有必要，我會試着更詳細地解釋這個問題，並感謝你在這個問題上提出的想法。

---

規範原題：假設算法一般工作（我已經檢查了好幾次）。所以我想我對Java的理解在程序的某些部分是不正確的。二認爲可能是有趣：

• 我打開所有的編譯器警告（感謝刪節）一個是左，The parameter configurations should not be assigned後，它的顯示Configure problem severity爲線combinations = childCombinations;。可能這是一個問題？
• 總是傳遞給該函數的變量combinations是否有可能在第二/第三/ ...遞歸調用中直接而不是在返回後更改？

在由程序產生的輸出返回下列組合的時刻（這顯然是不正確的）：

• [1，2，3，3，5，5，6，6， [1,2,3,4,5,7,7]
• [1,2,3,5,5,6,6,4,4,7,7]
• [ 5，6,6，4,4，7,7]
• [1，2，3，3，5，5，6，6,4，4,7，7]

感謝您的時間和精力！

Answer 1

因爲我無法清楚地解釋問題，所以無法發佈解決方案。現在我將發佈解決方案。首先，破壞驚喜：按照我的理解，該算法是正確的，但在整個遞歸過程中，同一個combinations變量被改變了。因爲這也產生了四次相同的組合。

解決方法是使用clone方法，因此將List更改爲LinkedList。

private LinkedList<Combination> recursiveConfiguration(LinkedList<Combination> combinations){ 

    for(Combination c: combinations){ 
     c.add(this); 
    } 

    // Iterate through all edges of the current node 
    for(Edge e: getEdges()){ 

     int type = e.getType();  

     if((type == 1) || (type == 2)){ 
      // If type is mandatory or optional. 

      // In this case getChildren always returns only one feature. 
      LinkedList<Combination> copyConfig = new LinkedList<>(); 

      for(Combination c: configurations){ 
       @SuppressWarnings("unchecked") 
       LinkedList<FeatureNode3> copy = (LinkedList<FeatureNode3>) c.getFeatureList().clone(); 
       Combination config = new Combination(); 
       config.setFeatureList(copy); 
       copyConfig.add(config); 
      } 

      FeatureNode3 child = e.getChildren().get(0);  
      LinkedList<Combination> childCombinations = child.recursiveConfiguration(copyConfig); 

      if(type == 1){ 
       // If type is mandatory 
       combinations = childCombinations; 
      }else{ 
       // If type is optional 
       combinations.addAll(childCombinations); 
      } 
     } 
    }   
    return combinations; 
} 

感謝您的時間和建議！

Answer 2

我認爲你在開始列表中添加節點到列表中每個組合的邏輯是錯誤的，它應該在事後完成。

正確的算法看起來是這樣的：

1. 打電話給你的根節點遞歸函數。返回組合列表。

2. 如果是葉節點，則返回僅包含該節點的組合列表。

3. 對於每條邊：使用子節點調用遞歸函數並保存結果。

4. 創建強制兒童的所有可能的組合。例如。有兩個強制性孩子，一個有11個組合，另一個有7個，你得到11 * 7 = 77個組合。你基本上構建了所​​有強制組合的交叉產品，這是更簡單的一步。如果節點沒有強制子節點，那麼它就是一個內部有一個空組合的列表（稍後將向其添加當前節點）。

5. 結合可選兒童的組合。例如。與兩個額外的可選兒童3和5組合，你得到77 + 77 * 3 + 77 * 5 + 77 * 3 * 5 = 1848組合。在這裏，您可以選擇是否採用可選分支，因此其爆炸速度非常快，具有3個分支a，b，c和x強制組合，您可以獲得x + ax + bx + cx + abx + acx + bcx + abcx（服用和不服用a，b或c的所有組合）。

6. 將調用函數的節點添加到每個組合並返回結果。