recursion - 递归地进行组合

问题描述

我有一个类似这样的层结构：

我想为每个项目输出所有可能的组合，但不包括顺序高于自身的项目，顺序是第一个数字，例如：

5.1会有以下组合：

(4.1, 3.1, 2.1, 1.1)  
(4.1, 3.1, 2.1, 1.2)  
(4.1, 3.2, 2.1, 1.1)   
(4.1, 3.2, 2.1, 1.2)

4.1将具有：

(3.1, 2.1, 1.1)  
(3.1, 2.1, 1.2)  
(3.2, 2.1, 1.1)   
(3.2, 2.1, 1.2)

我想用递归函数来做，我尝试了一些东西，但它不能正常工作，这里是伪代码。
我从图层顺序开始，然后向下直到它到达顺序为 1 的图层。

function recursion (layer)
    if layer.order > 1 do 
       for iterationLayer in allLayers do
          if iterationLayer.order == (layer.order - 1) do
              print iterationLayer.name
              recursion iterationLayer
    else
      end of combination

对于4.1案例，这段代码给了我类似的东西

(3.1, 2.1, 1.1) 
(1.2)
(3.2, 2.1, 1.1) 
(1.2)

之所以这样，是因为当递归到达最后一个 for 循环时，它会从底部追溯到顶部，是否有人对此有解决方案？

标签： recursionmatrixcombinationslayer

解决方案

伪代码：

    function recursionMain(level)
        for iterationLayer in allLayers where (layer.level == level)
            recursion (iterationLayer, new list)


    function recursion(currentLayer, currentLayerList)

        remainingLevelsList = get the distinct list of levels left to visit

        if remainingLevelsList not empty
           lowestRemamingLevel = get the lowest number from remainigLevelsList
           for iterationLayer in allLayers where (layer.level == lowestRemainingLevel)
              recursion (iterationLayer, currentLayerList + currentLayer)
        else
          print the list(combination) / end of combination

这是 C# 中的工作示例：

static void GetCombinationsR(int level)
{
    foreach (Layer layer in layers.Where(l => l.Level == level))
    {
        GetCombinationsR(layer, new List<Layer>());
    }
}

static void GetCombinationsR(Layer layer, List<Layer> currentLayers)
{
    // Declaring new list so we don't loose the list of previous layers in currentLayers
    List<Layer> currentLayers2 = new List<Layer>();
    currentLayers2 = currentLayers2.Union(currentLayers).ToList();
    currentLayers2.Add(layer);

    // Getting the list of remaining levels because we are not certain
    // if level 1 is the lowest or if some levels are skipped
    List<int> remainingLevels = layers.Select(l => l.Level).Where(l => l < layer.Level).ToList();
    if (remainingLevels.Count() > 0)
    {
        int firstLowerLevel = remainingLevels.OrderByDescending(l => l).First();

        foreach (Layer layerByValue in layers.Where(l => l.Level == firstLowerLevel).ToArray())
        {
            GetCombinationsR(layerByValue, currentLayers2);
        }
    }
    else
    {
        PrintResultList(currentLayers2);
    }
}


    static void PrintResultList(List<Layer> resultList)
    {
        StringBuilder sb = new StringBuilder();
        foreach (Layer layer in resultList)
        {
            sb.Append(layer.Level).Append(": ").Append(layer.Value).Append(" -> ");
        }
        sb = sb.Remove(sb.Length - 4, 4);
        Console.WriteLine(sb.ToString());
    }

recursion - 递归地进行组合

问题描述

解决方案

推荐阅读