I’ve spent the past few hours trying to find a way to recursively search a list for all possible combinations of size n and I think I finally have it:
def combinations(n, list, combos=): # initialize combos during the first pass through if combos is None: combos =  if len(list) == n: # when list has been dwindeled down to size n # check to see if the combo has already been found # if not, add it to our list if combos.count(list) == 0: combos.append(list) combos.sort() return combos else: # for each item in our list, make a recursive # call to find all possible combos of it and # the remaining items for i in range(len(list)): refined_list = list[:i] + list[i+1:] combos = combinations(n, refined_list, combos) return combos
['a', 'b', 'c', 'd']
['a', 'b'] ['a', 'c'] ['a', 'd'] ['b', 'c'] ['b', 'd'] ['c', 'd']
While this took way longer than it should have, and I’m sure it’s terribly inefficient, I’m satisfied that I was able to persevere until finally coming up with a working solution.
Update: So yeah, while this code works fine for small lists, it is entirely too inefficient for my original goal: finding all possible 5-letter combinations out of the 26-letter alphabet. To be honest, I’m feeling pretty discouraged that my solution doesn’t work, but I’m hoping the insight I seem to lack will come with more experience. I’d be lying if I didn’t acknowledge that it’s times like these that somewhere deep down I begin to question if I have what it takes for a career in programming. I’d love to talk to some more experienced programmers and hear their thoughts on the matter. Do all programmers have moments like this?
def find_least(file='words.txt'): alphabet ='a b c d e f g h i j k l m n o p q r s t u v w x y z'.split(' ') combos = combinations(5, alphabet) max = 0 max_combo = None for combo in combos: matches = filter_words(file, combo) if matches > max: max = matches max_combo = combo return (max, max_combo) def filter_words(file, forbidden): fin = open(file) matches = 0 for line in fin: word = line.strip() if avoids(word, forbidden): matches += 1 return matches
Update 2: I tried the same brute force method for testing all the possibilities by calculating the various combinations using itertools.combinations instead of my own function and the process still seemed to eat up all of my system resources, so that leads me to believe the bottleneck is likely my entire approach, not just the way in which I coded my combinations function. I’ve decided to put this problem aside for now and move on to something else.