Programming Questions

  • Newest
  • Popular Tags
  • Ask A Question
  • Transitivity Relations: I don't understand the question
    Transitivity Relations Challenge I've read the question multiple times and I don't see the transitive relationship. Can anyone break down the question? Or point me toward a resource to help me understand the question? Thanks!
    mattlarsh posted this question on 3/17/14 | transitivity, relation
    Answers
  • +
  • 2
  • -
  • 0:(1,1,0,0) means 0 connects to itself (0) and to 1 1:(0,0,1,0) means 1 connects to 2 2:(0,1,0,1) means 2 connects to 1 and to 3 3:(1,0,0,1) means 3 conncets to 0 and to 3 0 connects to 1 and 1 connects to 2, so there is a connection from 0 to 2 via 1. If that relation is transitive, that means, that there should also be a connection from 0 to 2, but in 0: (1,1,0,0) the third entry is 0, so there is no connection. So we add the connection (0,2).
  • +
  • 2
  • -
  • I understand that, but why when you have this array, ["(1,1,0,0)","(0,0,1,0)","(0,1,0,1)","(1,0,0,1)"], why do you need to add all these connections,(0,2)-(0,3)-(1,0)-(1,3)-(2,0)-(3,1)-(3,2), to make it transitive?
  • +
  • 1
  • -
  • In the example above you have to add (0,2) because(0,1) and (1,2) are connections in the original array. If you look at the original you wouldn't need a connection (0,3). However adding the (0,2) connection changes the original array to ["(1,1,1,0)", ...]. See why you need to add (0,3)?
  • +
  • 1
  • -
  • I got it. Thanks!
  • +
  • 1
  • -
  • The Input is ["(1,1,1)","(1,0,0)","(0,1,0)"] The first list element "(1,1,1)" represents the first node, the second list element "(1,0,0)" represents the second node. Each array entry in a node tells us if there is a connection to a node with that index. If input[0][2] ==1 then node 0 has a connection with node 2.
  • +
  • 0
  • -
  • Followup to Alex Black's answer: In the first example ["(1,1,1)","(1,0,0)","(0,1,0)"], you say the missing connections are (1,2)-(2,0). But I also count 1-1 (1->0, 0->1). And if you count the fact that you add those, as Alex's comment seems to confirm, you should add 2-2 as well. (2->1, 1->2) Is the example wrong or am I missing something? Thanks!
    Log in to write an answer.