标签: equivalence-classes

为什么当我改变下面工会中两套的顺序时,我会得到不同的结果？

set1 = {1, 2, 3}
set2 = {True, False}

print(set1 | set2)
# {False, 1, 2, 3}

print(set2 | set1)
#{False, True, 2, 3}

考虑有一些整数列表:

#--------------------------------------
0 [0,1,3]
1 [1,0,3,4,5,10,...]
2 [2,8]
3 [3,1,0,...]
...
n []
#--------------------------------------

问题是合并具有至少一个共同元素的列表.因此,仅给定部分的结果如下:

#--------------------------------------
0 [0,1,3,4,5,10,...]
2 [2,8]
#--------------------------------------

在大数据上执行此操作的最有效方法是什么(元素只是数字)？ 是tree结构一些思考？我现在通过将列表转换为sets迭代并迭代交叉来完成工作,但它很慢!而且我有一种如此初级的感觉!此外,实现缺少一些东西(未知),因为有些列表有时会保持未合并!话虽如此,如果你提出自我实现,请慷慨并提供一个简单的示例代码[显然Python是我的偏爱:)]或pesudo代码.
更新1: 这是我使用的代码:

#--------------------------------------
lsts = [[0,1,3],
        [1,0,3,4,5,10,11],
        [2,8],
        [3,1,0,16]];
#--------------------------------------

功能是(越野车!!):

#--------------------------------------
def merge(lsts):
    sts = [set(l) for l in lsts]
    i = 0
    while i < len(sts):
        j = i+1
        while j < len(sts):
            if len(sts[i].intersection(sts[j])) > 0:
                sts[i] = sts[i].union(sts[j])
                sts.pop(j)
            else: j += 1                        #---corrected
        i …

我有一个将一个数据库转换为另一个数据库的项目 其中一个原始数据库列定义行的类别.此列应映射到新数据库中的新类别.

例如,我们假设原始类别是:parrot, spam, cheese_shop, Cleese, Gilliam, Palin

现在这对我来说有点冗长,而且我希望将这些行分类为sketch, actor- 也就是说,将所有草图和所有actor定义为两个等价类.

>>> monty={'parrot':'sketch', 'spam':'sketch', 'cheese_shop':'sketch', 
'Cleese':'actor', 'Gilliam':'actor', 'Palin':'actor'}
>>> monty
{'Gilliam': 'actor', 'Cleese': 'actor', 'parrot': 'sketch', 'spam': 'sketch', 
'Palin': 'actor', 'cheese_shop': 'sketch'}

这很尴尬 - 我更喜欢这样的东西:

monty={ ('parrot','spam','cheese_shop'): 'sketch', 
        ('Cleese', 'Gilliam', 'Palin') : 'actors'}

但是,这当然将整个元组设置为关键:

>>> monty['parrot']

Traceback (most recent call last):
  File "<pyshell#29>", line 1, in <module>
    monty['parrot']
KeyError: 'parrot'

如何在Python中创建优雅的多对一字典？

谢谢,

亚当

对于自动机算法,我需要一种功能语言的快速Union-Find数据结构.由于我需要正式证明数据结构的正确性,我宁愿选择一个简单的结构.

我想要做的是计算一组S关系中元素的等价类R ? S × S.我想最终得到的是一些函数f: S ? S,它将任何元素映射S到其R等价类的(规范)代表.通过"规范",我的意思是我不关心它是什么代表,只要它对于一个等价类的所有元素都是相同的,即我想要f x = f y ? (x,y) ? R持有.

在函数式语言中,最好的数据结构和算法是什么？我应该补充一点,我真的需要"正常"的功能代码,即没有可变性/状态变换器monad.

编辑:与此同时,我提出了这个算法:

m := empty map
for each s ? S do
  if m s = None then
    for each t in {t | (s,t) ? R}
      m := m[t ? s]

这将创建一个映射,将任何元素映射S到其等价类的代表,其中代表是迭代所到达的第一个元素S.我认为这实际上有线性时间(如果地图操作是不变的).但是,我仍然对其他解决方案感兴趣,因为我不知道这在实践中有多高效.

(我的关系在内部表示为"S→(S Set)选项",因此迭代超过{t |(s,t)∈R} - 这是对该结构的廉价操作.)

Java有一个Comparator<T>用于提供类本身外部对象的比较,以允许进行有序比较的多种/替代方法.

但是,进行无序比较的唯一标准方法是equals() 在类中重写.

当我想在课堂外提供多个/备用无序比较时,我该怎么办？(明显的用例是根据特定属性将集合划分为等价类.)

假设最终用途是无序检查(例如不用于排序或索引),是否可以实现Comparator<T>只检查相等性,如果两个对象相等则返回0,当两个对象不相等时返回值!= 0？(注意:我没有跳过这个解决方案的唯一原因是,技术上它可以Comparator通过不提供满足传递性和对称性的关系来打破合同.)

似乎应该有一个EqualsComparator<T>标准的类或什么的.

(番石榴会处理这样的事吗？)

说我有一个有限的迭代X和等价关系~上X.我们可以定义一个my_relation(x1, x2)返回Trueif 的函数,否则x1~x2返回False.我想编写一个分区X为等价类的函数.也就是说,my_function(X, my_relation)应该返回一个等价类的列表~.

有没有一种标准的方法在python中执行此操作？更好的是,是否有一个旨在处理等价关系的模块？

我正在寻找一个良好的数据结构来在树的节点上构建等价类.在理想的结构中,以下操作应该是快速的(适当的O(1)/ O(n))和容易(没有神秘代码的段落):

• (A)从树上走树; 在每个节点上 - >子转换枚举子节点的所有等效版本
• (B)合并两个等价类
• (C)从现有节点(子节点)和其他数据的列表中创建新节点
• (D)找到结构上等同于节点的任何节点(即它们具有相同数量的子节点,相应的子节点属于相同的等价类,并且它们的"其他数据"相等)以便可以放置新的(或新修改的)节点在正确的等价类中(通过合并)

到目前为止,我已经考虑过(其中一些可以组合使用):

• parfait,其中子节点引用节点集合而不是节点.(A)速度快,(B)需要遍历树并更新节点以指向合并集合,(C)需要查找包含新节点的每个子节点的集合,(D)需要遍历树
• 按特征维护节点的哈希值.这使得(D)更快但(B)更慢(因为当合并等价类时必须更新散列)
• 将节点串在一起成为循环链表.(A)速度快,(B)速度快但是因为圆形列表的"合并"部分实际上拆分列表(C)会很快,(D)需要走树
• 如上所述,但在每个节点中有一个额外的"向上"指针,可用于查找循环列表的规范成员.

我错过了一个甜蜜的选择吗？

假设您有许多元素,并且需要跟踪它们之间的等价关系.如果元素A等价于元素B,则它等效于所有其他元素B等价.

我正在寻找一种有效的数据结构来编码这些信息.应该可以通过与现有元素的等价来动态添加新元素,并且从该信息中可以有效地计算新元素等效的所有元素.

例如,考虑以下元素[0,1,2,3,4]的等价集:

0 = 1 = 2
3 = 4

等号表示等价的.现在我们添加一个新元素5

0 = 1 = 2
3 = 4 
5

并强制执行等价5=3,数据结构变为

0 = 1 = 2
3 = 4 = 5

由此,人们应该能够有效地迭代任何元素的等价集.对于5,这个集合将是[3,4,5].

Boost已经提供了一个方便的数据结构disjoint_sets,似乎满足了我的大多数要求.考虑这个简单的程序,说明如何实现上面的例子:

#include <cstdio>
#include <vector>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/unordered/unordered_set.hpp>

/*
    Equivalence relations
    0 = 1 = 2
    3 = 4
 */

int main(int , char* [])
{
    typedef std::vector<int> VecInt;
    typedef boost::unordered_set<int> SetInt;

    VecInt rank (100);
    VecInt parent (100);
    boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]); …

我使用VS 2008,.net 3.5,C#项目.我需要在功能上像Microsoft.VisualBasic.FileIO.FileSystem.DeleteDirectory一样.

任何人都说在C#中引用Microsoft.VisualBasic通常是不受欢迎的.在C#代码中与VB的任何关联都让我觉得不可取.

使用FileSystem类,这是一个非常好的解决方案,但我不想引用Microsoft.VisualBasic库.那个我会避免的.

     private static void DeleteDirectory(string destino)
            {
    //UIOption Enumeration. Specifies whether to visually track the operation's progress. Default is UIOption.OnlyErrorDialogs. Required.

    //RecycleOption Enumeration. Specifies whether or not the deleted file should be sent to the Recycle Bin. Default is RecycleOption.DeletePermanently.

    //UICancelOption Enumeration. Specifies whether to throw an exception if the user clicks Cancel. Required.
                Microsoft.VisualBasic.FileIO.FileSystem.DeleteDirectory(destino, 
Microsoft.VisualBasic.FileIO.UIOption.OnlyErrorDialogs, 
Microsoft.VisualBasic.FileIO.RecycleOption.DeletePermanently, 
Microsoft.VisualBasic.FileIO.UICancelOption.ThrowException);
                //Directory.Delete(destino, true);
            }

其他示例: 如何将文件放在回收站而不是删除？

Microsoft.VisualBasic.FileIO.FileSystem.DeleteFile(file.FullName,
    Microsoft.VisualBasic.FileIO.UIOption.OnlyErrorDialogs,
    Microsoft.VisualBasic.FileIO.RecycleOption.SendToRecycleBin);

当在c ++中重载"=="运算符时,是否存在关于明确意味着什么的标准定义,或者"=="应如何表现的一组准则？

我目前有一个类不会将其整个自我存储在内存中.它基本上使用优先级队列来确定自身内部对象的使用频率,以及何时从队列末尾弹出对象,将它们从内存中删除并写入磁盘.

所以现在问题出现在相等的问题上,这两个对象的相同之处是什么意思.因为我们可以从对象A和B开始,它们在各方面都是相同的,所以它们将相同的数据加载到内存中,并且它们在磁盘上具有相同的数据.但是在调用A和B上的一系列函数后,它们现在可能会有所不同.A和B在磁盘上仍然具有相同的数据,但它们将不同的数据加载到内存中.那么问题应该A == B是真的还是假的？

是否有一套规则或指导方针来定义这应该如何运作？或者这只是我决定什么对程序最有意义并记录"=="的作用的情况？

gnu awk是否支持POSIX等价类？

是否可以使用awk匹配[[= a =]],就像在grep中完成一样？

$ echo ábÅ | grep [[=a=]]
ábÅ

$ echo ábÅ | grep -o [[=a=]]
á
Å