Преобразование нескольких строк Python в псевдокод - PullRequest
Новая
       43

Преобразование нескольких строк Python в псевдокод

0 голосов
/ 05 марта 2012

Цель: попытка преобразовать некоторые строки алгоритма, написанного на python, в псевдокод.

Цель данного алгоритма: найти все циклы в ориентированном графе с циклами.

ГдеЯ стою: я хорошо понимаю теорию, лежащую в основе алгоритма, я также сам написал разные версии, однако я не могу написать алгоритм, который бы был маленьким, эффективным и корректным сам по себе.

Источник: stackoverflow

Что я сделал до сих пор: я не могу описать, сколько недель провел на нем, закодировал Tarjan, различные версии DFS, Flloyd и т. Д. В php, но, к сожалению, они являются лишь частичными решениями, и нужнорасширить их больше.

Кроме того: я запустил этот алгоритм в сети, и он сработал, он мне нужен для школьного проекта, который я использую в стеке, и не могу продолжить.

Это алгоритм: 

def paths_rec(path,edges):
    if len(path) > 0 and path[0][0] == path[-1][1]:
        print "cycle", path
        return #cut processing when find a cycle

    if len(edges) == 0:
        return

    if len(path) == 0:
        #path is empty so all edges are candidates for next step
        next_edges = edges
    else:
        #only edges starting where the last one finishes are candidates
        next_edges = filter(lambda x: path[-1][1] == x[0], edges)

    for edge in next_edges:
        edges_recursive = list(edges)
        edges_recursive.remove(edge)
        #recursive call to keep on permuting possible path combinations
        paths_rec(list(path) + [edge], edges_recursive)


def all_paths(edges):
    paths_rec(list(),edges)

if __name__ == "__main__":
    #edges are represented as (node,node) 
    # so (1,2) represents 1->2 the edge from node 1 to node 2. 
    edges = [(1,2),(2,3),(3,4),(4,2),(2,1)]
    all_paths(edges)

Это то, что мне удалось написать из него в псевдокоде, я пометил #? не понятными мне строками.Как только я получу их в псевдокоде, я смогу кодировать их в php, с которым я хорошо знаком. 

procedure paths_rec (path, edges)

if size(path) > 0 and path[0][0] equals path[-1][1] 
    print "cycle"
    for each element in path
        print element
    end of for
    return
end of if


if size(edges) equals 0
    return
end of if

if size(path) equals 0
    next_edges equals edges
else
    next edges equals filter(lambda x: path[-1][1] == x[0], edges) #?
end of else  

for each edge in next_edges
edges_recursive = list(edges) #?
edges_recursive.remove(edge)#?
#recursive call to keep on permuting possible path combinations
paths_rec(list(path) + [edge], edges_recursive)#?

1 Ответ

1 голос
/ 05 марта 2012

Линия next_edges = filter(lambda x: path[-1][1] == x[0], edges) создает новый список, содержащий ребра в edges, первая точка которых совпадает со второй точкой последнего элемента текущего пути и эквивалентна 

next_edges = []
for x in edges:
    if path[len(path) - 1][1] == x[0]
        next_edges.append[x]

Линии создают новую копию списка ребер edges, поэтому при удалении edge из этой копии список не изменяется edges

edges_recursive = list(edges)
edges_recursive.remove(edge)

paths_rec(list(path) + [edge], edges_recursive)это просто рекурсивный вызов с путем с добавленным в конец edge и новым списком ребер, из которого удален edge.

...