Понимание списков (Transitiv)
Мне нужно написать функцию Python isReflexive и isSymmetric, которые являются эксклюзивными для Python List Comprehension и функции all or any. Пример:
isSymmetric([2,3,4],[(2,3),(3,2),(3,3),(2,4),(4,2)])
True
isTransitive([[2,3,4,5],[(2,3),(3,2),(3,3),(3,4),(2,4),(4,2),(2,2),(4,4),(4,3)]
Истинный
Аргумент 1 представляет собой базовый набор (список), а аргумент 2 представляет собой отношение к этому базовому набору.
Я пробовал это, но это не работает, потому что я также проверяю кортежи, которые мне не нужно проверять:
def isSymmetric(g,r):
return all([(x,y) = r for x in g for y in g])
Я не знаю, как решить проблему... И isTransitiv я не знаю как запустить D:
Заранее спасибо за помощь!
Ответы 1
Следующие реализации на основе comp/gen будут работать для симметрии и транзитивности:
from itertools import product
def isSymmetric(g, r):
s = set(r)
return all(x[::-1] in s for x in s)
def isTransitive(g, r):
s = set(r)
return all(
((x,y) in s and (y,z) in s) <= ((x,z) in s)
for x, y, z in product(g, repeat=3)
)
Оба не идеальны с алгоритмической точки зрения. Лучше (меньше и быстрее проверок) было бы:
def isSymmetric(g, r):
s = set(r)
while s:
x, y = s.pop()
if x != y: # (x, x) does not need a partner
try:
s.remove((y, x))
except KeyError: # reverse not there!
return False
return True
Проверка транзитивности немного сложнее. Вы можете использовать вспомогательную структуру данных (collections.defaultdict), чтобы сделать все проверки постоянными, а не линейными:
def isTransitive(g, r):
d = defaultdict(set)
for x, y in r:
d[x].add(y)
for x in g: # `for x in d` reduces iterations in the general case
for y in d[x]: # all (x, y)
if not all(z in d[x] for z in d[y]): # exists (x, z) for (y, z)?
return False
return True
Я знаю, что такое транзитивность и симметрия, но я хочу выполнять функцию только со списками и любыми или всеми. Я уже пробовал это без каких-либо или всех и списков понятий. Я знаю, как это работает, но я хочу знать, что это работает со списками.....
Зачем понимание, если у вас может быть генератор, который делает то же самое без использования памяти?
Это действительно должно быть return all((x,x) in r for x in g)
Я знаю, что он работает со списками, но я не знаю, как его запрограммировать. Я уже запрограммировал рефлексив... и теперь хочу запрограммировать транзитивность и симметрию
Первый — это поиск симметрии, не так ли?
Я добавил варианты на основе comp/gen. Однако обратите внимание, что проверка транзитивности, в частности, будет быстро ухудшаться для больших доменов и отношений.
Да, но разве это не должно выглядеть так, если я хочу использовать только списки? def isSymmetric(g, r): return all(x[::-1] in set(r) for x in set(r))
Если «единственное понимание» настолько узко, что вы готовы вводить всевозможные ужасные антишаблоны (создавая множество снова и снова и снова...). Тогда вообще лучше не использовать сет: return all(x[::-1] in r for x in r)
Извините за столько вопросов. Я учу себя Python и на одном сайте эти задачи были без решений и я хочу узнать, как это работает. То, что вы написали, мне помогло. Большое спасибо. Только функцию с isTransitive мне немного сложно понять.
Вы, вероятно, имели в виду часть a in s and b in s <= c in s часть. Из логики утверждений мы знаем, что «если a ^ b, то c» неверно только в том случае, если «a ^ b» истинно, а «c» ложно. В логических значениях Python этим единственным случаем будет a and b > c, поскольку True > False (1 > 0). Так что это верно, если a and b <= c ;-)
Вы предварительно проконсультировались со своим учебником, учителем и т. д.?