pythonで関係を与えられた等価クラスにinterableを分割する標準的な方法はありますか？

Question

私はXという有限の反復可能性とXの同値関係~を持っているとします。関数my_relation(x1, x2)を定義して、の場合はTrueを返し、それ以外の場合はFalseを返します。等価クラスにXを分割する関数を記述したいと思います。つまり、my_function(X, my_relation)は、等価クラスのリストを~として返す必要があります。

Pythonでこれを行う標準的な方法はありますか？さらに、等価関係を扱うように設計されたモジュールはありますか？バイナリ機能については

Answer 1

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はブール値を返す場合ああ、これは明らかに動作しません。私は最初にこれをやろうとするのが目的だとは思うが、それぞれの同形性を表現するための抽象的な方法を考え出すといいだろう。

Answer 2

ジョンリード氏によるthis Python recipeが見つかりました。これはPython 2で書かれていて、それをPython 3に適合させてテストしました。レシピには、lambda x, y: (x - y) % 4 == 0という関係に基づいて等価クラスに整数のセット[-3,5)を分割するテストが含まれています。

あなたがしたいようです。ここで私はあなたは、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() 

Answer 3

次の関数は、反復可能な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]] 

Answer 4

これは機能しますか？

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}] 

EDIT：あなたは、これは可能な限り高速に実行したい場合、あなたは可能性があります

を
• これをCythonモジュールにラップします（defaultdictを削除します。mucはありません）。変更するには、時間のもの）
• は、私は同値関係を扱う任意のPythonライブラリを認識していないよ

Answer 5

（いずれかを見つけることができませんでした）専用のモジュールを見つけるPyPy

でそれを実行してみたいです。

はおそらく、このスニペットは便利です：

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