-1

所以这是我用 Python 编写的第一批程序之一。我正在尝试获取一个字符串，并输出所有真实单词的字符串。我已经完成了（我需要找到一个包含更多单词的参考文件）但是它不可扩展，因为我不能输入超过 8 个字符，而 Python 需要很长时间才能返回一些东西。

def lower_and_remove_spaces(fill_string):
    '''
    function takes a string of 2 or more characters and prints out all the permutations
    of words that the characters can make. 
    '''
    lower_string = ''

    for i in fill_string:
        if i.isalpha():
            lower_string += i.lower()

    return lower_string    

def fill_list(input_string):
   iter_list = []
   string_list = []
   this_string = lower_and_remove_spaces(input_string)
   for num in range(2,len(this_string)+1):
      iter_list.append(itertools.permutations(this_string,num))

   for iters in iter_list:
      for lists in iters:
         string_list.append(list(lists))

    return string_list

def word_list(string):
   string_list = fill_list(string)
   a_word_list = []
   a_string = ''
   for i in string_list:
      if not a_string == '':
         a_word_list.append(a_string)
      a_string = ''
      for y in i:
         a_string += y
    return a_word_list

我知道这会跳很多，但我想知道有什么更好的方法来做到这一点，以便它具有可扩展性？

4

1 回答 1

5

一些快速的想法：使所有排列都变成 O(n!)，没有办法解决这个问题。即使您优化了代码，当 n 接近更大的数字时，您仍然会碰壁。如果你有一本有效词的字典，这个问题就有点不同了。在病态输入集（您的字典包含所有排列）下，您没有比这更好的了。

但是，您可以执行以下操作

  1. 将有效单词字典保存在前缀树中
  2. 手动递归生成排列，而不是通过 itertools.ie，选择一个字母，开始一个单词，递归
  3. 在每一步，检查前缀是否有效，否则修剪搜索树。

这在实践中的性能将比 O(n!)

如果你不熟悉前缀树，这里有一种方法可以用 Python 哈希来模拟相同的东西

   def prefix_hash(list_o_words):
       ret = {}
       for word in list_o_words:
           for i in range(2,len(word)-1):
               ret[word[:i]] = 'prefix'  # this should check if it's a word first..
       ret[word] = 'word'

如果您需要更多帮助，请提出问题。

于 2012-08-13T03:52:36.293 回答