Programming Questions

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 **|**

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).

vimes123

answered on 03/20/14

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?

mattlarsh

answered on 03/20/14

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)?

AlexBlack

answered on 03/21/14

1

I got it. Thanks!

mattlarsh

answered on 03/20/14

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.

vimes123

answered on 03/20/14

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!

illiptic

answered on 09/24/15

Log in to write an answer.