<p>上述解决方案失败的原因是</p>
<ul>
<li><code>Counter</code>以无序的方式返回三元组,因此,如果您多次运行解决方案,您也将随机获得所需的解决方案</li>
<li>当你找到这个组合的时候,你就返回它,你既不能按长度的顺序去做,也不能在所有的组合中找到满足问题的最佳组合</li>
</ul>
<p>在这里,我将按照包含三元组列表的最小到最高的顺序进行,然后在找到解决方案后立即返回。在</p>
<pre><code>from itertools import permutations
def checkTrigramsPresentInList(trigrams_list,input_list):
for input_string in input_list:
flag = False
for trigram in trigrams_list:
if trigram in input_string:
flag = True
if not flag:
return False
return True
def ngrams(text, n=3):
return [text[i:i + n] for i in range(len(text) - n + 1)]
def identifying_grams(input_list, n=3):
trigrams = []
for item in input_list:
trigrams += ngrams(item)
len_of_trigrams = len(trigrams)
trigrams_unique = list(set(trigrams))
idx =1
correct_tri_lists = []
unique_trigrams_list = []
while idx <= len_of_trigrams:
trigrams_lists = permutations(trigrams_unique,idx)
for trigrams_list in trigrams_lists:
print(trigrams_list)
if not trigrams_list in unique_trigrams_list:
if checkTrigramsPresentInList(list(trigrams_list),input_list):
correct_tri_lists.append(list(trigrams_list))
##Uncomment below lines if only one combination is needed
if correct_tri_lists:
return correct_tri_lists
unique_trigrams_list.append(trigrams_list)
idx = idx+1
list1 = ['amsterdam','rotterdam','haarlem','utrecht','groningen']
print(identifying_grams(list1))
# # Good, we get: ['ter', 'haa', 'utr', 'gro']
list2 = ['amsterdam','schiedam']
print(identifying_grams(list2))
# # Good, we get: ['dam']
list3 = ['amsterdam','schiedam','terwolde','wolstad']
print(identifying_grams(list3))
</code></pre>