樹結構算法

Question

我的程序有問題。例如，我有5個字段。這些字段的值爲true或false。 False字段可以刪除。所以我想找到這些領域的所有可能的組合。

我的想法是：比如我有這些領域

• 字段1的XML，真正
• 字段2，真正
• 字段3，假
• 字段4，假
• 字段5，假的

結果應該是：

{Field1, Field2, Field3, Field4, Field5} 
{Field1, Field2,  , Field4, Field5} 
{Field1, Field2,  ,  , Field5} 
{Field1, Field2,  ,  ,  } 
{Field1, Field2, Field3,  , Field5} 
{Field1, Field2, Field3,  ,  } 
{Field1, Field2, Field3, Field4,  } 
{Field1, Field2,  , Field4,  } 

8個組合。

而我的想法是，它可以用樹狀結構解決。我將檢查當前字段是「真」還是「假」。如果「真」，那麼我會向前移動一個字段。如果該字段爲「false」，我將複製XML並使用當前的「false」字段添加一次，並在列表中添加一次。 像這裏的圖片一樣。

public List<List<Fieldmatrix>> permut(List<Fieldmatrix> matrix, int j) { 

    while (felderLaenge != j) { 

     if (!matrix.get(j).isTrue()) { 
      tmpL = iterateLeft(matrix, j); 

      tmpR = iterateRight(matrix, j); 


     } else { 
      tmpL = iterateRight(matrix, j); 

     } 
     j++; 
     return permut(tmpL, j); 
    } 
    return sammlung; 
} 

iterateLeft手段刪除，iterateRight表示不刪除。

我不能實現duplicate-Function。所以我只有4個Xmls結果：
{1,2,3,4,5}, {1,2,4,5}, {1,2,3,5}, {1,2,3,4}

有人能幫助我嗎？

---

首先，我很感謝您的第一次支持。

的Fieldmatrix級的樣子：

public class Fieldmatrix { 

private String feld; 
private boolean pflicht; 

public Fieldmatrix(String feld, boolean pflicht){ 
    this.feld = feld; 
    this.pflicht = pflicht; 
} 

public String getFeld() { 
    return feld; 
} 

public void setFeld(String feld) { 
    this.feld = feld; 
} 

public boolean isPflicht() { 
    return pflicht; 
} 

public void setPflicht(boolean pflicht) { 
    this.pflicht = pflicht; 
} 

}

我怎樣才能改變這一部分「prefixWithField.add（？）」 你用字符串處理它，這工作，因爲這份名單是也是String類型。 但我使用列表 。

iterateRight（）僅打印控制檯。 ieterateLeft（）刪除當前字段並用控制檯打印。

Answer 1

問題

有多種問題：

• 如果您當前的樹節點有兩個孩子的，你必須下降到兩個，而不僅僅是左邊。
• 最後，您返回了sammlung（engl。collection），但從未添加任何元素（至少不在所提供的代碼中）。
• 與遞歸結合的while循環似乎有點奇怪。但是我不能在沒有看到iterateLeft和iterateRight的情況下多說這些。

實施

實現的功能將如下所示的快捷方式。 爲簡單起見，Fieldmatrix類被String所取代。

public static List<List<String>> combine(List<String> fields) { 
    return combine(fields, 0, new ArrayList<>()); 
} 

public static List<List<String>> combine(List<String> fields, 
             int start, List<String> prefix) { 
    List<List<String>> combinations = new ArrayList<>(); 
    if (start >= fields.size()) { 
     combinations.add(prefix); 
     return combinations; 
    } 
    String field = fields.get(start); 
    if (field.contains("false")) { 
     combinations.addAll(combine(fields, start + 1, prefix)); 
    } 
    List<String> prefixWithField = new ArrayList<>(prefix); 
    prefixWithField.add(field); 
    combinations.addAll(combine(fields, start + 1, prefixWithField)); 
    return combinations; 
} 

該實現不是非常有效。許多中間結果被一遍又一遍地複製。

例

List<String> fields = new ArrayList<>(); 
fields.add("1:true"); 
fields.add("2:true"); 
fields.add("3:false"); 
fields.add("4:false"); 
fields.add("5:false"); 
combine(fields).forEach(c -> System.out.println(c)); 

打印

 
[1:true, 2:true] 
[1:true, 2:true, 5:false] 
[1:true, 2:true, 4:false] 
[1:true, 2:true, 4:false, 5:false] 
[1:true, 2:true, 3:false] 
[1:true, 2:true, 3:false, 5:false] 
[1:true, 2:true, 3:false, 4:false] 
[1:true, 2:true, 3:false, 4:false, 5:false]