假设您有一个单词列表：
['cat', 'ant', 'bro', 'gro']
使用我们自己构造的一些任意映射{'c'=>'a', 'a'=>'n', 't'=>'t' }，我们可以将"cat"映射到"ant"，同样，我们可以找到一些任意映射来将"bro"转换为"gro"。
这就是寻找对等单词的想法。我写了一个函数来比较两个单词，并通过我在飞行中构建的映射来检查它们是否等效：
def compareWords(w1, w2):
mapping = {}
for i in xrange(0, len(w1)):
if w1[i] in map:
if mapping[w1[i]] == w2[i]:
continue
else:
return False
else:
mapping[w1[i]] = w2[i]
return True
示例输入：
['cat', 'ant', 'bro', 'gro']
示例输出：
[['cat','ant'], ['bro', 'gro']]
对列表中的每一对单词使用此函数以返回等效单词列表的输出列表在O（n^2）中运行，因为每对单词都需要进行比较。我还没有实现这一部分，我在输入列表上使用上面的方法并生成输出列表，因为这种方法不是我想要的有效比较。有没有办法在O（n）时间内找到这个输入列表中的等价词？
进一步解释：如果我有一个单词列表，并且我想找到所有"等效"单词，我需要成对地进行检查。如果我正在比较的单词的所有字母都是唯一的，那么如果第二个单词中的所有字母也是唯一的，则列表中的另一个单词仅等同于第一个单词。因此，如果xyz在列表中，则abc可以映射到xyz。如果xyz在列表中，则xyz可以映射到pqr。考虑到这一点，abc、xyz和pqr都是等价的。这就是我要找的那种分组。
如果我理解正确，您正在寻找一种方法来检查任意关系（以对x,y的列表形式给出）是否是函数，也就是说，x1==x2意味着y1==y2。这可以很容易地通过设置完成：
def is_function(rel):
return len(set(rel)) == len(set(x for x, y in rel))
print is_function(['ab', 'cd', 'xd']) # yes
print is_function(['ab', 'cd', 'ad']) # no
如果两个词的字母对字母关系是一个函数，那么在你的问题中，这两个词是"等价的"：
def equivalent(a, b):
return is_function(zip(a, b))
print equivalent('foo', 'baa') # yes
print equivalent('foo', 'bar') # no
如果你认为不同单词之间的等价关系是不同的关系，那么你就无法避免将每个单词与每个单词进行比较。此外，你的"等价"甚至不是交换的，A ~ B并不意味着B ~ A（例如abc ~ xyx，而是xyx !~ abc）。
从您的评论来看，您的关系是双射的（注意：您的代码不适合这种情况）。将列表拆分为"等价类"的最简单（不一定是最有效的）方法是为每个单词计算一个"哈希"，将字母替换为数字，其中0代表第一个字母，1代表第二个字母等：
def eq_hash(word):
return tuple(word.index(c) for c in word)
print eq_hash('mom') # 0 1 0
print eq_hash('dad') # 0 1 0
现在，您可以将所有具有相同"hash"的单词组合在一起。在你的问题中，这些将是等效的：
group = {}
words = ['mom', 'dad', 'aaa', 'bob', 'ccc', 'xyz', 'abc']
for w in words:
h = eq_hash(w)
group[h] = group.get(h, []) + [w]
print group.values()
# [['xyz', 'abc'], ['mom', 'dad', 'bob'], ['aaa', 'ccc']]
如果我理解您的请求，您希望对单词进行分组，使每个关系都是唯一的，而不一定是唯一的。使用您的示例，mom ~ dad ~ bab，但bad不可能存在于该集合中，因为没有可以从妈妈映射到爸爸（m->d，o->a）或爸爸映射到bab（d->b，a->a）的映射可以映射到bad（对于妈妈，m->b和d？对于爸爸，d到b一次，然后跳过下一次？）。
假设你的分组真的是交换的，那么一旦你对一个单词进行了分组，你就不应该重新访问它，除非对照每组的第一个单词。
所以，你应该先把你的第一个单词添加到你的第一组中。然后，对于每个额外的单词，您需要将其与每个现有组中的第一个单词进行比较——如果匹配，则将其添加到组中；如果它与任何组都不匹配，则将其添加到自己的新组中。
在最坏的情况下，这是O（N**2），如果集合中的每个单词都属于自己的组。在最好的情况下，如果你的集合中的所有单词都在第一组中，那么它将是O（N），因为你只会将唯一一组中的第一个单词与每个额外的单词进行比较。如果你有一个对数（N）分布的集合，这个算法实际上是O（N log（N））。因此，这取决于您的输入集，但与检查每一对相比，它将导致更少的比较。