python - 从排序的单词列表中高效打印匹配的 semordnilaps 对

Question

我正在研究从给定的按字母顺序排序的单词(或短语)列表(假定为小写)中打印所有匹配的 semordnilaps 对的问题。

semordnilap 被定义为向后拼写不同 单词(或短语)的单词(或短语)。所以 'top'('pot' 向后读)，'avid'('diva' 向后读)和'动物'('lamina' 向后读)是 semordnilaps，'semordnilap' 本身也是，因为它是 '回文' 倒读，而 'tot'、'peep'、'radar' 是回文(倒读相同的单词)但不是semordnilaps。在此上下文中，一对单词 'word1' 和 'word2' 匹配 如果 'word1' 是 'word2' 向后读(反之亦然)。

如果输入列表的长度是 N 那么解决方案显然会复杂 O(N(N-1)/2) 因为有 可以构造 N(N-1)/2 个不同的对。此外，如果列表按字母顺序排序，那么在最坏的情况下似乎必须检查所有 N(N-1)/2 对以找到所有匹配对。

我想知道是否有比直接方法更有效的方法。目前，这是我的代码。

import io

def semordnilaps_in_text_file( file_path ):

    def pairup( alist ):
        for elem1 in range( len( alist ) ):
            for elem2 in range( elem1 + 1 , len( alist ) ):
                yield ( alist[elem1], alist[elem2] )

    def word_list( file_path ):
        thelist = []
        with io.open( file_path, 'r', encoding='utf-8' ) as file:
            for line in file:
                thelist.append( line.strip() )
        return thelist

    for word1, word2 in pairup( word_list( file_path ) ):
        if word1[::-1] == word2:
            print '{} {}'.format( word1, word2 )

我用找到的(全部小写)英文单词列表尝试了这个函数 here (包含 109583 个单词)，在我打断它之前，几分钟后设法打印了以下 21 对。

abut tuba
ac ca
ados soda
agar raga
ah ha
ajar raja
al la
am ma
an na
animal lamina
ante etna
ape epa
are era
ares sera
as sa
assam massa
ate eta
avid diva
aw wa
bad dab
bag gab

Answer 1

您只需要跟踪您看到的单词。

def pairup(alist):
  seen = set()
  for word in alist:
    if word not in seen:
      # Haven't seen this one yet
      if word[::-1] in seen:
        # But we've seen its reverse, so we found a pair
        yield (word, word[::-1])
      # Now we've seen it
      seen.add(word)

微妙之处:将新找到的单词添加到最后的 seen 可以避免在遇到回文时触发 yield。相反，如果您还想检测回文，请在检查反射是否已经存在之前将单词添加到 seen。

此外:无需将单词读入列表即可使用该功能。您可以只为它提供一个可迭代对象，例如列表理解:

for word, drow in pairup(line.strip().lower()
                         for line in io.open(filepath, 'r')):
  print('{} {}'.format(word, drow))