Генерация двумерного массива чисел, вложенных в словарь - PullRequest
Новая
       37

Генерация двумерного массива чисел, вложенных в словарь

0 голосов
/ 21 сентября 2018

У меня есть словарь, содержащий некоторые ключи в виде чисел.Каждый ключ имеет набор значений, которые содержат числа, «вложенные» в этот конкретный ключ (эти данные были извлечены из базы данных).

Некоторые примеры:

  • 825имеет 838 внутри, а внутри 838 - 2941, а внутри 2941 - 556. Итак, 4 вложенных уровня.

  • 825 содержит 27, что является только одним вложенным уровнем.

  • 23 вложено в 838 (2 вложенных уровня), но в 23 есть 66, поэтому 3 вложенных уровня.

пример структуры: 

dictionary {
    825 : [838, 27],
    838 : [2941, 23],
    2941 : [556, 612],
    23 : [66]
}

Я написал некоторый код, который может получить числа, вложенные в другие числа, так как одно из требований состоит в том, чтобы понять, насколько глубокой является вложенность. 

// example: call function with key: 825
public int getDepth(int number, Dictionary<int, List<int>> nestedNumbers, int depth)
{
    // 825 is in nestedNumbers
    if (nestedNumbers.Keys.Contains(number))
    {
        // foreach number in 825 [838, 27]
        foreach (var currentNumber in nestedNumbers[number])
        {
            // depth is now level 2
            depth++;
            // call the function again but with 838, which will now get nested groups in 838 [2941, 23]
            return getDepth(currentNumber, nestedNumbers, depth);
        }
    }
    return depth;
}

Мне нужносоставить список списков (или список массивов), которые содержат все вложенные уровни, например: 

lvl1  lvl2  lvl3  lvl4
[[825, 838, 2941, 556],
[825, 27],   
[825, 838, 23, 66],
[825, 838, 2941, 612]]  <-- e.g. 612 is in 2941, 2941 is in 838, 838 is in 825

Но я не уверен, как это сделать, основываясь на функции, которая у меня уже естьнаписано.У кого-нибудь есть идеи, как мне этого добиться?

1 Ответ

0 голосов
/ 21 сентября 2018

Это проблема обхода дерева .В терминологии tree мы хотим, чтобы все пути от корня дерева до листьев или узлов, которые не имели дочерних элементов.Вот визуализация вашего дерева: 

       825
      /   \
     838   27
    /  \
  2941  23 
  /  \   \
556  612  66

Этот обход может быть выполнен с использованием стек или очередь структура данных (рекурсия основана на стеке) для выполненияобход.Я решил использовать очередь в этом примере.

Обходная часть включает в себя постановку в очередь дочерних элементов текущего узла и использование словаря для отслеживания родительского элемента каждого дочернего элемента, затем удаление очереди из очереди дочерних элементов один за другим и повторение процесса до достижения конечного узла.Как только такой узел обнаружен, путь к корню можно построить, перейдя обратно к дереву до достижения корня и добавив путь в список результатов. 

using System;
using System.Collections.Generic;

class MainClass {
    public static void Main(string[] args) {
        Dictionary<int, List<int>> tree = new Dictionary<int, List<int>>()
        {
            {825, new List<int> {838, 27}},
            {838, new List<int> {2941, 23}},
            {2941, new List<int> {556, 612}},
            {23, new List<int> {66}},
        };

        foreach (var row in FindPathsToLeaves(825, tree))
        {
            foreach (var cell in row) 
            {
                Console.Write(cell + " ");
            }

            Console.WriteLine();
        }
    }

    static List<List<int>> FindPathsToLeaves(int root, Dictionary<int, List<int>> tree)
    {
        List<List<int>> paths = new List<List<int>>();
        Dictionary<int, int> parent = new Dictionary<int, int>();
        parent[root] = -1;
        Queue<int> q = new Queue<int>();
        q.Enqueue(root);

        while (q.Count > 0) 
        {
            int current = q.Dequeue();

            if (tree.ContainsKey(current))
            {
                foreach (int n in tree[current])
                {
                    parent[n] = current;
                    q.Enqueue(n);
                }
            } 
            else
            {
                List<int> path = new List<int>();

                while (parent.ContainsKey(current))
                {
                    path.Insert(0, current);
                    current = parent[current];
                }

                paths.Add(path);
            }
        }

        return paths;
    }
}

Вывод: 

825 27 
825 838 2941 556 
825 838 2941 612 
825 838 23 66

Вот repl для тестирования.

...