Создание комбинаций рекурсивно - PullRequest
Новая
       50

Создание комбинаций рекурсивно

0 голосов
/ 08 июня 2018

У меня есть структура слоя, которая выглядит примерно так: 

   1.1   
   1.2  
   2.1  
   3.1  
   3.2  
   4.1  
   5.1

Я хочу вывести все возможные комбинации для каждого элемента, но не включая элементы с более высоким порядком, чем они сами, порядок является первым числом,так, например:

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 case 

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

Это так, потому что когда рекурсия достигает последнего цикла forон прослеживает снизу вверх, у кого-нибудь есть решение для этого?

Ответы [ 2 ]

0 голосов
/ 08 июня 2018

Псевдокод: 

    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());
    }
0 голосов
/ 08 июня 2018

Возможно, вам нужно что-то вроде этого: 

function recursion (layer, combination)
    if layer = 0
          print combination
    else
       for (i = 0; i < layer.itemcount; i++)   
          recursion(layer - 1, combination + layer.item[i])

recursion(layer-1, empty[])

Пример Delphi (не оптимальный, мы можем быстрее искать и прерывать цикл раньше) 

var
  A: TArray<string>;

  procedure recursion (layer: Integer; combination: string);
  var
    i: integer;
  begin
    if layer = 0 then
       Memo1.Lines.Add(combination)
    else
       for i := 0 to High(A) do
          if A[i][1] = IntToStr(layer) then //primitive check of layer
              recursion(layer - 1, combination + A[i] + ', ')
  end;


begin
  A := ['1.1','1.2','2.1','3.1','3.2','4.1','5.1'];
  recursion(4, '');

generates

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,
...