title: Is there a better algorithm for exercise 9.3 in 《Think Python: How to Think Like a Computer Scientist》
body: <p>The <a href="http://www.greenteapress.com/thinkpython/html/thinkpython010.html#toc101" rel="nofollow">exercise 9.3</a> in this book ask the reader to find a combination of 5 forbidden letters that excludes the smallest number of words in <a href="http://thinkpython.com/code/words.txt" rel="nofollow">this file</a>.</p>
  
  <p>Below is my solution for the first part, I think there is no problem for them</p>
  
  <pre><code># if the word contain any letter in letters, return True,
  # otherwise return False
  def contain(word, letters):
      for letter in letters:
          if letter in word:
              return True
      return False
  
  # return the number of words contain any letter in letters
  def ncont(words, letters):
      count = 0
      for word in words:
          if contain(word, letters):
              count += 1
  return count
  </code></pre>
  
  <p>But for the question above, I can only think of a brute-force algorithm, that is, try every kind of possible combination, there are exactly 26! / 5! = 65780 kind of combination, below is the implementation:</p>
  
  <pre><code>def get_lset(nlt, alphabet, cur_set):
      global min_n, min_set
      # when get enough letters 
      if nlt &lt;= 0:
          cur_n = ncont(words, ''.join(cur_set))
          if min_n == -1 or cur_n &lt; min_n:
              min_n = cur_n
              min_set = cur_set.copy()
          print(''.join(cur_set), cur_n, ' *-&gt;', min_n, ''.join(min_set))
      # otherwise find the result letters in a recursive way
      else:
          cur_set.append(None)
          for i in range(len(alphabet)):
              cur_set[-1] = alphabet[i]
              get_lset(nlt-1, alphabet[i+1:], cur_set)
          cur_set.pop()
  </code></pre>
  
  <p>and then call the above function like this:</p>
  
  <pre><code>if __name__ == '__main__':
      min_n = -1
      min_set = []
      with open('words.txt', 'r') as fin:
          words = [line.strip() for line in fin]
      get_lset(5, list(string.ascii_lowercase), [])
      print(min_set, min_n)
  </code></pre>
  
  <p>but this solution is very slow, and I'd like to know is there a better algorithm for this question? Any suggestion will be good!</p>