Python: Как сделать рекурсию в Python, используя вложенные функции min и max? - PullRequest
Новая
       16

Python: Как сделать рекурсию в Python, используя вложенные функции min и max?

0 голосов
/ 20 апреля 2019

Этот вопрос является расширением моего запроса , который я разместил на math.stackoverflow. Теперь, когда я понимаю работу алгоритма, я пытаюсь реализовать его на Python.

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

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

def td(G):                                  # G is an input connected graph
    G_copy = G.copy()
    nodesList = list(G.nodes)

    if (len(G_copy.nodes) == 1):
        depth = 1                           # Base case for the recursion
    else:
#        G_copy.remove_node(next(iter(nodesList), None))
#        depth = 1 + min(max([iter], key), key)  # Recursive step

    return depth

Мои вопросы:

  1. Могут ли min и max быть вложены вышеупомянутым способом, чтобы сократить алгоритм?
  2. В любом случае, как это можно реализовать?

Ответы [ 2 ]

0 голосов
/ 21 апреля 2019

Если кому-то интересно, это рабочая реализация алгоритма.Он не имеет вложенных min и max, но работает и также занимает много времени из-за сложности O (2 ^ n).

def td(G):

    copG = G.copy()
    depth = 0

    if (len(copG.nodes) == 1):
        depth = 1

    elif (len(copG.nodes) > 1 and nx.is_connected(copG)):
        someList = []

        for v in list(copG.nodes)[:-1]:
            edges = list(copG.edges(v))
            copG.remove_node(v)            
            someList.append(td(copG))
            copG.add_node(v)
            copG.add_edges_from(edges)

        depth = 1 + min(someList)

    elif(len(copG.nodes) > 1 and not nx.is_connected(copG)):
        someList2 = []
        for i in (copG.subgraph(c) for c in nx.connected_components(copG)):
            someList2.append(td(i))

        depth = max(someList2)


    return depth
0 голосов
/ 20 апреля 2019

Вот решение: вы передаете минимальное и максимальное значение в качестве параметра в рекурсивную функцию, как показано ниже: 

my_array = [0, 1, 2, 3, 4, [3, 4, 5, 6, [5, 6, 7, 8, 9]]]


def get_min_max(my_list, min_val=False, max_val=False):
    for num in my_list:
        if isinstance(num, list):
            min_val, max_val = get_min_max(num, min_val, max_val)
        else:
            if min_val is False or num < min_val:
                min_val = num
            if max_val is False or num > max_val:
                max_val = num
    return min_val, max_val


min_num, max_num = get_min_max(my_array)

print(min_num, max_num)

выход 

0 9
...