组合算法

Question

这是程序：

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

我的想法是：例如，我有一个包含这些字段的 XML

• 字段 1，真
• 字段 2，真
• 字段 3，假
• 字段 4，假
• 字段 5，假

结果是：

{字段 1， 字段 2， 字段 3， 字段

• 4， 字段 5}
{字段 1， 字段 2， ， 字段
• 4， 字段 5}
• {字段 1， 字段 2， ， ， 字段 5}
• {字段 1， 字段 2， ， ， }
• {字段 1， 字段 2， 字段 3， ， 字段 5}
• {字段 1， 字段 2， 字段 3， ， }
• {字段 1， 字段 2， 字段 3， 字段 4， }
• {字段 1， 字段 2， ， 字段 4， }

这些字段的值为 true 或 false。可以删除假字段。因此，程序可以找到这些字段的所有可能组合。

字段矩阵：

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

该程序仅适用于"一维"列表，这意味着如果任何字段在他自己的列表中没有字段。

我想更新此代码。 现在我有一个这样的结构：

• 字段 1，真
• 字段 2，真
• 字段 3，假
  • 子字段 1，真
  • 子字段 2，真
    • 子字段 1，假

子字段1 和子字段 2 位于字段 3 的列表中。子字段 1 位于子字段 2 中。

我应该如何更改代码，以便适用于更多维度的示例？

有人有想法吗？

Answer 1

假设顺序无关紧要，您可以使用一种方法来生成可选的所有组合(即在您的情况下为 FALSE 参数)，如下所示：

假设您有 3 个可选参数和 2 个强制参数。 所以你将有 3^2 = 9 种组合。

现在，您所要做的就是迭代 9 次以生成所有可能的组合。

只是一个伪代码：

您的选项： ["A"， "B"， "C"] 3^2=9种可能性。

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

您可以谷歌检查是否设置了特定位。

希望这足以让你开始。 万事如意。