Блог

Главная - Вопросы по программированию - Понимание списков (Transitiv)

Понимание списков (Transitiv)

#python #list #function #list-comprehension #any

#python #Список #функция #понимание списка #Любой

Вопрос:

Мне нужно написать функцию Python isReflexive и isSymmetric, которые являются эксклюзивными для понимания списка Python и функции all или 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. Вы сначала консультировались со своим учебником, учителем и т. Д.?

Ответ №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)
    )

Оба не идеальны с точки зрения алгоритмического POV. Лучше (меньше и быстрее проверок) было бы:

 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

Комментарии:

1. Я знаю, что такое транзитивность и симмертия, но я хочу выполнять функцию только с пониманием списка и любым или всеми. Я уже пробовал это без каких-либо или всех и перечислений. Я знаю, как это работает, но я хочу знать, что это работает с пониманием списков…..

2. Зачем понимание, если у вас может быть генератор, который делает то же самое без использования памяти?

3. Это действительно должно быть return all((x,x) in r for x in g)

4. Я знаю, что это работает с пониманием списков, но я не знаю, как его запрограммировать. Я уже запрограммировал reflexiv … и теперь я хочу запрограммировать transititv и symmetric

5. Первый — это то, что стремится к симметрии, не так ли?

Метки: