0

I'm having trouble figuring out how to determine if this list is transitive or not

D1 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}

I have to determine if r in the domain of D1 is transitive. I have to check every possible tuple

What I have so far

def r(x, y):
    R = [[9, 7], [9, 5], [9, 3], [9, 1], [7, 5], [7, 3], [7, 1], [5, 3], [3, 1]]
    return([x, y] in R)

rIsTransitive = True

for a in D1:
    for b in D1:
        for c in D1:
            for d in D1:
                if(r(a, b) and b == c):
                    rIsTransitive = False
                    print('The triple (' + str(a) + ',' + str(b) + ',' + str(c) + ') shows that r is not transitive')


if (rIsTransitive):
    print('The relation r on domain D1 is transitive.')
else:
    print('The relation r on domain D1 is not transitive.')
print(' ')

The output should be

The triple (5,3,1) shows that r is not transitive
The relation r on domain D1 is not transitive.

My output currently

The triple (9,5,5) shows that r is not transitive
The triple (9,5,5) shows that r is not transitive
The triple (9,5,5) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The triple (9,7,7) shows that r is not transitive
The relation r on domain D1 is not transitive.
2

2 Answers 2

1

Through you defind all [X,Y] in R which X>Y, and you want the output be (5,3,1), you could modify the condition and add the statement to stop the loop.

def r(x, y):
    R = [[9, 7], [9, 5], [9, 3], [9, 1], [7, 5], [7, 3], [7, 1], [5, 3], [3, 1]]
    return([x, y] in R)

rIsTransitive = True

for a in D1:
    for b in D1:
        for c in D1:
            if(r(a, b) and b > c):
                rIsTransitive = False
                print('The triple (' + str(a) + ',' + str(b) + ',' + str(c) + ') shows that r is not transitive')
                break
        if rIsTransitive == False:
            break


if (rIsTransitive):
    print('The relation r on domain D1 is transitive.')
else:
    print('The relation r on domain D1 is not transitive.')
print(' ')
1

Given comment clarification from Mark Dickinson,

You can iterate trough your list and unpack your sub arrays in one go with for a,b in s

then you need 2 loops (see bellow) , one for the first pair, one for the second. Because your set is ordered, you only need to check that b == c and that the array [a,d] is in the set, then you need to output a,b,d because otherwise you will see a triplet with b==c.

Assuming you want to stop right after the first non transitive item (5,3,1) then you can break out of the for loop (need a flag and conditional break everyway... or you could use a generator function)

s = [[9, 7], [9, 5], [9, 3], [9, 1], [7, 5], [7, 3], [7, 1], [5, 3], [3, 1]]

def my_non_transitivity_genenerator(value_set):
    for a,b in s:
        for c,d in s:
            yield (b==c and [a,d] not in s,a,b,c,d)

checker = my_non_transitivity_genenerator(s)

for t,a,b,c,d in checker:
    if t:
        print(f'The triple ({a},{b},{d}) is not transitive')
        break
else:
    print('The relation r on domain D1 is transitive.')
1
  • 1
    This doesn't help the OP: (3, 1, 1) does not represent a "non-transitive item". As the OP clearly states, the algorithm should identify (5, 3, 1) as the problematic triple (because r(5, 3) is True and r(3, 1) is True, but r(5, 1) is False, while for a transitive relation r, if r(a, b) is true and r(b, c) is true then r(a, c) must also be true). The problem is that the OP is not using the correct test for transitivity in the first place. Commented Aug 12, 2021 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.