Есть ли стандартный способ разбить целое на классы эквивалентности с учетом отношения в Python?
Скажем, у меня есть конечная итерация X и отношение эквивалентности ~ на X, Мы можем определить функцию my_relation(x1, x2) это возвращает True если x1~x2 и возвращается False иначе. Я хочу написать функцию, которая разделяет X в классы эквивалентности. То есть, my_function(X, my_relation) должен вернуть список классов эквивалентности ~,
Есть ли стандартный способ сделать это в Python? Еще лучше, есть ли модуль, предназначенный для работы с отношениями эквивалентности?
6 ответов
Следующая функция принимает итеративный aи функция эквивалентности equivи делает то, что вы спрашиваете:
def partition(a, equiv):
partitions = [] # Found partitions
for e in a: # Loop over each element
found = False # Note it is not yet part of a know partition
for p in partitions:
if equiv(e, p[0]): # Found a partition for it!
p.append(e)
found = True
break
if not found: # Make a new partition for it.
partitions.append([e])
return partitions
Пример:
def equiv_(lhs, rhs):
return lhs % 3 == rhs % 3
a_ = range(10)
>>> partition(a_, equiv_)
[[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]]
Я нашел этот рецепт Питона от Джона Рида. Он был написан на Python 2, и я протестировал его на Python 3. Рецепт включает в себя тест для разбиения набора целых чисел [-3,5) в классы эквивалентности на основе отношения lambda x, y: (x - y) % 4 == 0,
Кажется, делать то, что вы хотите. Вот адаптированная версия, которую я сделал на тот случай, если вы захотите ее в Python 3:
def equivalence_partition(iterable, relation):
"""Partitions a set of objects into equivalence classes
Args:
iterable: collection of objects to be partitioned
relation: equivalence relation. I.e. relation(o1,o2) evaluates to True
if and only if o1 and o2 are equivalent
Returns: classes, partitions
classes: A sequence of sets. Each one is an equivalence class
partitions: A dictionary mapping objects to equivalence classes
"""
classes = []
partitions = {}
for o in iterable: # for each object
# find the class it is in
found = False
for c in classes:
if relation(next(iter(c)), o): # is it equivalent to this class?
c.add(o)
partitions[o] = c
found = True
break
if not found: # it is in a new class
classes.append(set([o]))
partitions[o] = classes[-1]
return classes, partitions
def equivalence_enumeration(iterable, relation):
"""Partitions a set of objects into equivalence classes
Same as equivalence_partition() but also numbers the classes.
Args:
iterable: collection of objects to be partitioned
relation: equivalence relation. I.e. relation(o1,o2) evaluates to True
if and only if o1 and o2 are equivalent
Returns: classes, partitions, ids
classes: A sequence of sets. Each one is an equivalence class
partitions: A dictionary mapping objects to equivalence classes
ids: A dictionary mapping objects to the indices of their equivalence classes
"""
classes, partitions = equivalence_partition(iterable, relation)
ids = {}
for i, c in enumerate(classes):
for o in c:
ids[o] = i
return classes, partitions, ids
def check_equivalence_partition(classes, partitions, relation):
"""Checks that a partition is consistent under the relationship"""
for o, c in partitions.items():
for _c in classes:
assert (o in _c) ^ (not _c is c)
for c1 in classes:
for o1 in c1:
for c2 in classes:
for o2 in c2:
assert (c1 is c2) ^ (not relation(o1, o2))
def test_equivalence_partition():
relation = lambda x, y: (x - y) % 4 == 0
classes, partitions = equivalence_partition(
range(-3, 5),
relation
)
check_equivalence_partition(classes, partitions, relation)
for c in classes: print(c)
for o, c in partitions.items(): print(o, ':', c)
if __name__ == '__main__':
test_equivalence_partition()
Я не знаю ни о какой библиотеке Python, имеющей дело с отношениями эквивалентности.
Возможно, этот фрагмент полезен:
def rel(x1, x2):
return x1 % 5 == x2 % 5
data = range(18)
eqclasses = []
for x in data:
for eqcls in eqclasses:
if rel(x, eqcls[0]):
# x is a member of this class
eqcls.append(x)
break
else:
# x belongs in a new class
eqclasses.append([x])
eqclasses
=> [[0, 5, 10, 15], [1, 6, 11, 16], [2, 7, 12, 17], [3, 8, 13], [4, 9, 14]]
Будет ли это работать?
def equivalence_partition(iterable, relation):
classes = defaultdict(set)
for element in iterable:
for sample, known in classes.items():
if relation(sample, element):
known.add(element)
break
else:
classes[element].add(element)
return list(classes.values())
Я попробовал это с:
relation = lambda a, b: (a - b) % 2
equivalence_partition(range(4), relation)
Который вернулся:
[{0, 1, 3}, {2}]
РЕДАКТИРОВАТЬ: Если вы хотите, чтобы это работало как можно быстрее, вы можете:
- оберните его в модуль Cython (удаляя defaultdict, не нужно много чего менять)
- хочу попробовать запустить его с PyPy
- найти выделенный модуль (не смог найти ни одного)
In [1]: def my_relation(x):
...: return x % 3
...:
In [2]: from collections import defaultdict
In [3]: def partition(X, relation):
...: d = defaultdict(list)
...: for item in X:
...: d[my_relation(item)].append(item)
...: return d.values()
...:
In [4]: X = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
In [5]: partition(X, my_relation)
Out[5]: [[3, 6, 9, 12], [1, 4, 7, 10], [2, 5, 8, 11]]
Для двоичной функции:
from collections import defaultdict
from itertools import combinations
def partition_binary(Y, relation):
d = defaultdict(list)
for (a, b) in combinations(Y):
l = d[my_relation(a, b)]
l.append(a)
l.append(b)
return d.values()
Вы можете сделать что-то вроде этого:
partition_binary(partition(X, rank), my_relation)
О, это, очевидно, не работает, если my_relation возвращает логическое значение. Я бы сказал, придумайте какой-то абстрактный способ представления каждого изоморфизма, хотя я подозреваю, что это цель попытки сделать это в первую очередь.
Библиотека NetworkX, похоже, имеет встроенную функцию . Может быть, вы можете использовать его.