Write an algorithm in Python which takes a prufer code as input and returns the edge set of the tree. Input: a list named "p" (the prufer code, zero-indexed) Example:
p = [3,1,0,0,3,2,9,9,2,3]
(The prufer code can be defined within the code block. You do not need to write a function which takes user input) Output: a list named "edges" (the edge set_ Example:
print(edges)
[[3, 4], [1, 5], [0, 1], [0, 6], [3, 0], [2, 7], [9, 8], [9, 10], [2, 9], [3, 2], [3,11]]
I am having trouble with this. How can i get the values for "p" so that it prints the output in "edges"?
Great algorithm from David Eisenstat. Some nitpicks:
.pop(0) is linear on lists: I would prefer to make the list traversal more explicit by replacing the while with a for ... enumerate;.difference() would not require to convert the second operand into a set;min() and max() are a little overkill, since we know that the remaining set has exactly two elements.def decode(p):
p = list(p)
vertices = set(range(len(p) + 2))
for (i, u) in enumerate(p):
v = min(vertices.difference(p[i:]))
vertices.remove(v)
yield u, v
yield tuple(vertices)
print(list(decode([3, 1, 0, 0, 3, 2, 9, 9, 2, 3])))
Output:
[(3, 4), (1, 5), (0, 1), (0, 6), (3, 0), (2, 7), (9, 8), (9, 10), (2, 9), (3, 2), (3, 11)]