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
  4. # 10/10 points (graded)
  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:
  23.     g.addNode(n)
  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.
  35. g.addEdge(Edge(nodes[0], nodes[1]))
  36. g.addEdge(Edge(nodes[0], nodes[2]))
  37. g.addEdge(Edge(nodes[1], nodes[4]))
  38. g.addEdge(Edge(nodes[2], nodes[3]))
  39. g.addEdge(Edge(nodes[3], nodes[5]))
  40. g.addEdge(Edge(nodes[4], nodes[5]))
  41.  
  42.  
  43. # correctCorrect
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top