通過任意映射查找列表中相同的單詞

Question

假設你有一個單詞列表：我們構建自己{'c'=>'a', 'a'=>'n', 't'=>'t' }

['cat', 'ant', 'bro', 'gro'] 

使用一些隨意的映射，我們可以映射「貓」到「蟻族」，同樣我們可以找到一些任意的映射來將'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）中運行的等價單詞列表的輸出列表，因爲每對將需要t o比較。我沒有實現這個部分，我在輸入列表中使用了上面的這個方法，並且生成了輸出列表，因爲這個方法不是我期待的有效比較。有沒有辦法在O（n）時間在這個輸入列表中找到相同的單詞？

進一步解釋： 如果我有一個單詞列表，我想找到所有的「等價物」的話，我需要做的檢查，在雙字。如果我比較的單詞中的所有字母都是唯一的，那麼如果第二個單詞中的所有字母都是唯一的，則列表中的另一個單詞只與第一個單詞相同。所以如果xyz在列表中，abc可以映射到xyz。如果xyz在列表中，xyz可以映射到pqr。鑑於此，abc，xyz和pqr都是等效的。這是我正在尋找的那種分組。

Answer 1

如果我理解正確，您正在尋找一種方法來檢查是否存在一個任意關係，作爲配對的列表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 

現在，您可以將所有具有相同「散列」的單詞組合在一起。這些將是你的問題的情況下相當於：

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

Answer 2

如果我明白你的要求，你要組詞，使得每一種關係可能是唯一的，並不一定是它是獨一無二的。因爲沒有可以從媽媽到爸爸（m-> d，o-> a）或爸爸映射到bab（d-> b，）的映射，所以使用你的例子，媽媽爸爸， a-> a）可以映射爲壞的（對於媽媽來說，m-> b AND d？對於父親來說，d到b有一次並跳過下一個？）。

假設你的分組真的是可交換的，那麼只要你分組了一個單詞，你就不應該重新訪問它，除非檢查每個組的第一個單詞。

所以，你首先要把你的第一個單詞加到你的第一個組中。然後，對於每個附加單詞，您需要將其與每個現有組中的第一個單詞進行比較 - 如果匹配，則將其添加到組;如果它不匹配任何組，則將其添加到它自己的新組。

在最壞的情況下，這是O（N ** 2），如果你的集合中的每個單詞屬於它自己的組。在最好的情況下，如果你的集合中的所有單詞都在第一組中結束，那麼它將是O（N），因爲你只會將唯一組中的第一個單詞與每個附加單詞進行比較。如果你有一個log（N）分佈的集合，這個算法實際上是O（N log（N））。所以，這取決於你的輸入設置，但是如果你檢查每一對，比較結果會少得多。