Question: I'm trying to create a function best_tiles which takes in the number of tiles in your hand and returns the set of tiles that allows you to produce the most number of unique English-valid words, assuming that you can only use each tile once. For example, with the set of tiles in your hand (A, B, C) you can produce the words, CAB, BAC, AB, and BA (all of these are English words), so you can spell 4 unique words with that set. With (B, A, A), you can spell 5 words: ABA, BAA, AA, AB, and BA. The goal is to find the set of letters which allows you to spell the most number of English-Valid words (without replacement). So if 5 was the maximum number of words that could be spelled with any combination of letters for N = 3, running best_tiles( n = 3 ) would return B, A, A. I'm wondering how to implement this efficiently? My current approach doesn't scale well at all with number of letters. I read in a wordlist. In this case, I'm using enable.txt here: https://www.wordgamedictionary.com/enable/ import os path = "enable.txt" words = [] with open(path , encoding='utf8') as f: for values in f: words.append(list(values.strip().upper()))  I create a function word_in_tiles h/t smack89 which returns whether it is possible to construct a word given a tile set: def word_in_tiles(word, tiles): tiles_counter = collections.Counter(tiles) return all(tiles_counter.get(ch, 0) == cnt for ch,cnt in collections.Counter(word).items())  I then create a function get_all_words which produces a list of all the possible words one can spell from a word list and a tile set. def get_all_words(tile_set, words): # words is a word list return [i for i in words if word_in_tiles(i, tile_set)]  The extremely naive approach for identifying which tileset is the "best" for three letters is the following: I first create a list of every possible combination for a given length. So for length 3, I'd do: import string import itertools letters = string.ascii_lowercase all_three_letter_combinations = list(itertools.combinations_with_replacement(letters, 3)) # Create a list of only words that are three letters are less three_letter = [i for i in words if len(i) <= 3] sequence_dict = dict() for i in all_three_letter_combinations: string_test = "".join(i).upper() sequence_dict[i] = get_all_words(string_test, three_letter)  Then remove the values with no length and sort by the length of the result: res = {k: v for k, v in sequence_dict.items() if len(v) >= 1} def GetMaxLength(res): return max((len(v), v, k) for k, v in res.items())[1:]  GetMaxLength(res) You get that, for three letters, the tile-set that produces the most english valid words is T A E which can produce the following words ['AE', 'AT', 'ATE', 'EAT', 'ET', 'ETA', 'TA', 'TAE', 'TEA'] I'd like to be able to scale this up to as big as N = 15. What is the best procedure for doing this?

Answer: I think this is good enough! Here is a log of my code running under PyPy: 0:00:00.000232 E 0:00:00.001251 ER 0:00:00.048733 EAT 0:00:00.208744 ESAT 0:00:00.087425 ESATL 0:00:00.132049 ESARTP 0:00:00.380296 ESARTOP 0:00:01.409129 ESIARTLP 0:00:03.433526 ESIARNTLP 0:00:10.391252 ESIARNTOLP 0:00:25.651012 ESIARNTOLDP 0:00:56.642405 ESIARNTOLCDP 0:01:57.257293 ESIARNTOLCDUP 0:03:55.933906 ESIARNTOLCDUPM 0:07:17.146036 ESIARNTOLCDUPMG 0:10:14.844347 ESIARNTOLCDUPMGH 0:13:34.722600 ESIARNTOLCDEUPMGH 0:18:14.215019 ESIARNTOLCDEUPMGSH 0:22:47.129284 ESIARNTOLCDEUPMGSHB 0:27:56.859511 ESIARNTOLCDEUPMGSHBYK 0:46:20.448502 ESIARNTOLCDEUPMGSHBYAK 0:57:15.213635 ESIARNTOLCDEUPMGSHIBYAT 1:09:55.530180 ESIARNTOLCDEUPMGSHIBYATF 1:18:35.209599 ESIARNTOLCDEUPMGSHIBYATRF 1:21:54.095119 ESIARNTOLCDEUPMGSHIBYATRFV 1:20:16.978411 ESIARNTOLCDEUPMGSHIBYAOTRFV 1:14:24.253660 ESIARNTOLCDEUPMGSHIBYAONTRFV 1:00:37.405571  The key improvements are these.  I distinguish not only between letters, but how many times the letter has been seen. Therefore every letter I can accept or move on. That was an idea I got while commenting on David Eisenstat's solution. From him I also got the idea that pruning trees out that can't lead to an answer controls the growth of the problem surprisingly well. The very first solution that I look at is simply all the top letters. This starts as a pretty good solution so despite it being depth first, we will prune pretty well. I am careful to consolidate "exhausted tries" into a single record. This reduces how much data we have to throw around.  And here is the code. import os import datetime path = "enable.txt" words = [] with open(path) as f: for values in f: words.append(values.strip().upper()) key_count = {} for word in words: seen = {} for letter in word: if letter not in seen: seen[letter] = 0 key = (letter, seen[letter]) if key not in key_count: key_count[key] = 1 else: key_count[key] += 1 seen[letter] += 1 KEYS = sorted(key_count.keys(), key=lambda key: -key_count[key]) #print(KEYS) #print(len(KEYS)) KEY_POS = {} for i in range(len(KEYS)): KEY_POS[KEYS[i]] = i # Now we will build a trie. Every node has a list of words, and a dictionary # from the next letter farther in the trie. # BUT TRICK:, we will map each word to a sequence of numbers, and those numbers # will be indexes into KEYS. This allows us to use the fact that a second 'e' is # unlikely, so we can deal with that efficiently. class Trie: def __init__(self, path): self.words = [] self.dict = {} self.min_pos = -1 self.max_pos = -1 self.words = [] self.count_words = 0 self.path = path def add_word (self, word): trie = self poses = [] seen = {} for letter in word: if letter not in seen: seen[letter] = 0 key = (letter, seen[letter]) poses.append(KEY_POS[(key)]) seen[letter] += 1 sorted_poses = sorted(poses); for i in range(len(sorted_poses)): trie.count_words += 1 pos = sorted_poses[i] if pos not in trie.dict: trie.dict[pos] = Trie(trie.path + KEYS[pos][0]) if trie.max_pos < pos: trie.max_pos = pos trie = trie.dict[pos] trie.count_words += 1 trie.words.append(word) base_trie = Trie('') for word in words: base_trie.add_word(word); def best_solution (size): def solve (subset, pos, best, partial): found = sum(x[0] for x in partial) upper_bound = sum(x[1] for x in partial) if size <= len(subset) or upper_bound < best or len(KEYS) <= pos: return (found, subset) if best < found: best = found # Figure out our next calculations. partial_include = [] partial_exclude = [] finalized_found = 0 for this_found, this_bound, this_trie in partial: if this_trie is None: # This is a generic record of already emptied tries finalized_found += this_found elif pos in this_trie.dict: include_trie = this_trie.dict[pos] partial_include.append(( this_found + len(include_trie.words), include_trie.count_words + this_found, include_trie )) # We included the tally of found words in the previous partial. # So do not double-count by including it again partial_include.append(( 0, this_bound - include_trie.count_words - this_found, this_trie )) partial_exclude.append(( this_found, this_bound - include_trie.count_words, this_trie )) elif this_found == this_bound: finalized_found += this_found else: partial_include.append(( this_found, this_bound, this_trie )) partial_exclude.append(( this_found, this_bound, this_trie )) if 0 < finalized_found: partial_include.append( (finalized_found, finalized_found, None) ) partial_exclude.append( (finalized_found, finalized_found, None) ) found_include, subset_include = solve(subset + [pos], pos+1, best, partial_include) if best < found_include: best = found_include found_exclude, subset_exclude = solve(subset, pos+1, best, partial_exclude) if found_include < found_exclude: return (found_exclude, subset_exclude) else: return (found_include, subset_include) count, subset = solve([], 0, 0, [(len(base_trie.words), base_trie.count_words, base_trie)]) return ''.join([KEYS[x][0] for x in subset]) for i in range(20): start = datetime.datetime.now() print(best_solution(i)) print(datetime.datetime.now() - start)