Algorithm for combinations

2
votes

This is the Programm:

    public List<List<Fieldmatrix>> permute(List<Fieldmatrix> fields, int start, List<Fieldmatrix> prefix) {

    List<List<Fieldmatrix>> combinations = new ArrayList<>();

        if (start >= fields.size()) {
            combinations.add(prefix);
            return combinations;
        }
        String field = fields.get(start).getFieldName();
        if (fields.get(start).isMandatory() == false) {
            combinations.addAll(combine(fields, start + 1, prefix));
        }
        List<Fieldmatrix> prefixWithField = new ArrayList<>(prefix);
        prefixWithField.add(new Fieldmatrix (field, fields.get(start).isMandatory(), fields.get(start).getFieldtype(), new ArrayList<>()));
        combinations.addAll(combine(fields, start + 1, prefixWithField));

        return combinations;
    }

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

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

The results are:

  • {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, }

The fields have the value true or false. False fields can be deleted. So the program finds every possible combination of these fields.

Fieldmatrix:

public class Fieldmatrix {

private String fieldName;
private boolean mandatory;
private Type fieldtype;
private List<Fieldmatrix> list = new ArrayList<>();

public Fieldmatrix(String fieldName, boolean mandatory, Type fieldtype, List<Fieldmatrix> list){
    this.fieldName = fieldName;
    this.mandatory = mandatory;
    this.fieldtype = fieldtype;
    this.list = list;
}
//Getters and Setters

This program works only for "1-dimensional" Lists, this means if any field has no fields in his own list.

I want to update this code. Now I have a structure like this:

  • Field 1, true
  • Field 2, true
  • Field 3, false
    • Subfield 1, true
    • Subfield 2, true
      • Subsubfield 1, false

Subfield 1 and Subfield 2 are in the list of Field 3. Subsubfield 1 is in Subfield 2.

How should I Change the code, so that works for more dimensional examples?

Has anybody an Idea?

1
javaxmlalgorithmcombinationspermutation

1 Answers

0
votes

Assuming the order doesn't matter, you can use a way to generate all combinations of optional (i.e. FALSE params in your case) as follows:

Let's say you have 3 optional params, and 2 compulsory params. So you will have 3^2 = 9 combinations.

Now, all you have to do is iterate 9 times to generate all possible combinations.

Just a pseudo code:

Your options: ["A", "B", "C"] 3^2=9 possibilities.

for(i=0;i<9;i++){
  for(j=0;j<options.length;j++){
    if(j'th bit is set in 'i')
      print(options[j]);
  }
}

You can google to check if a particular bit is set or not.

Hope this is enough to get you started. All the best.