Tree-structure Algorithm

Question

I have problems with my program. For example I have 5 fields. The fields have the value true or false. False fields can be deleted. So I want to find every possible combination of these fields.

My Idea was: For example I have an XML with these fields

• Field1, true
• Field2, true
• Field3, false
• Field4, false
• Field5, false

The result should be:

{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 Combinations.

And my idea was, it could solved with a tree-structure. I will check whether current field is "true" or "false". If "true" then I will move a field forward. If the field is "false" I will duplicate the XML and add once with the current "false" field and once without it in a list. Like on the picture here for example.

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 means delete, iterateRight means do not delete.

I can´t implement the duplicate-Function. So I have only 4 Xmls results:
{1,2,3,4,5}, {1,2,4,5}, {1,2,3,5}, {1,2,3,4}

Could someone help me?

---

First of all I am thankful for your first support.

The Fieldmatrix-Class look like:

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

}

How can I change this part "prefixWithField.add(?)" You handle it with String and this works because the List is also type of String. But I work with List .

iterateRight() prints only with the console. ieterateLeft() deletes the current field and prints with the console.

Answer 1

Problems

There are multiple problems:

• If your current tree node has two childs, you have to descend into both, not just the left one.
• At the very end, you returned sammlung (engl. collection), but never added any elements (at least not in the presented code).
• The while loop combined with the recursion seems somewhat odd. But I cannot say much about this without looking at iterateLeft and iterateRight.

Implementation

A quick way to implement the function would be as follows. For simplicity, the Fieldmatrix class was replaced by 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;
}

This implementation is not very efficient. A lot of intermediate results are copied over and over again.

Example

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

prints

[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]