• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Sep 23rd, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # Exercise 2
2.
3. # Exercise 2
5. # Consider our representation of permutations of students in a line from Exercise 1. (The teacher only swaps the positions of two
6. # students that are next to each other in line.) Let's consider a line of three students, Alice, Bob, and Carol (denoted A, B, and C).
7. # Using the Graph class created in the lecture, we can create a graph with the design chosen in Exercise 1: vertices represent
8. # permutations of the students in line; edges connect two permutations if one can be made into the other by swapping two adjacent
9. # students.
10.
11. # We construct our graph by first adding the following nodes:
12.
13. nodes = []
14. nodes.append(Node("ABC")) # nodes[0]
15. nodes.append(Node("ACB")) # nodes[1]
16. nodes.append(Node("BAC")) # nodes[2]
17. nodes.append(Node("BCA")) # nodes[3]
18. nodes.append(Node("CAB")) # nodes[4]
19. nodes.append(Node("CBA")) # nodes[5]
20.
21. g = Graph()
22. for n in nodes:
24. # Add the appropriate edges to the graph.
25.
26. # Hint: How to get started?
27. # Write your code in terms of the nodes list from the code above. For each node, think about what permutation is allowed. A permutation
28. # of a set is a rearrangement of the elements in that set. In this problem, you are only adding edges between nodes whose permutations
29. # are between elements in the set beside each other. For example, an acceptable permutation (edge) is between "ABC" and "ACB" but not
30. # between "ABC" and "CAB".
31.
32.
33. # Write the code that adds the appropriate edges to the graph
34. # in this box.