从以下树型数据结构中获取所有可能的组合

在下面的内容中，您将看到一个数据结构，它与特征模型的简化版本非常相似（对于它们来看看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]

感谢您的时间和精力！

来源

2017-04-20 So S

请阅读并遵守帮助文档中的发布准则。 [最小，完整，可验证的示例]（http://stackoverflow.com/help/mcve）适用于此处。在发布您的MCVE代码并准确描述问题之前，我们无法为您提供有效的帮助。我们应该能够将给定的代码发布到文件中，运行该文件并重现问题。 – Prune

看到这个可爱的[debug]（https://ericlippert.com/2014/03/05/how-to-debug-small-programs/）博客寻求帮助。 – Prune

@Prune：我了解MCVE指南。此外，我试图按照博客文章中的描述来调试代码。不过，问题是要求设计算法的帮助，而不是解决编程错误。执行的结果并不是如此，我坚持了。我已经添加了算法的解释并将问题标记为更具体。感谢您的反馈。 –

因为我无法清楚地解释问题，所以无法发布解决方案。现在我将发布解决方案。首先，破坏惊喜：按照我的理解，该算法是正确的，但在整个递归过程中，同一个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; 
}

感谢您的时间和建议！

来源

2017-04-24 15:30:04

实际上，'LinkedList'只有一个真实生活案例 - 当您在巨大列表中间执行许多插入/删除操作时。在其他sutuations中，更喜欢'ArrayList'。要复制副本，使用'List newList = new ArrayList（oldList）'而不是'clone（）'，因为后者目前很少使用，而且在自定义实现中很少受到支持。 –

我认为你在开始列表中添加节点到列表中每个组合的逻辑是错误的，它应该在事后完成。

正确的算法看起来是这样的：

打电话给你的根节点递归函数。返回组合列表。
如果是叶节点，则返回仅包含该节点的组合列表。
对于每条边：使用子节点调用递归函数并保存结果。
创建强制儿童的所有可能的组合。例如。有两个强制性孩子，一个有11个组合，另一个有7个，你得到11 * 7 = 77个组合。你基本上构建了所有强制组合的交叉产品，这是更简单的一步。如果节点没有强制子节点，那么它就是一个内部有一个空组合的列表（稍后将向其添加当前节点）。
结合可选儿童的组合。例如。与两个额外的可选儿童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的所有组合）。
将调用函数的节点添加到每个组合并返回结果。

来源

2017-04-21 18:15:21 maraca

从以下树型数据结构中获取所有可能的组合

回答

相关问题