anagram_dfs.py

#!/usr/bin/env python3

from collections import Counter
import sys

def subset(a, b):
	'''Checks if a is subset of b'''
	for k in a:
		if k not in b or b[k] < a[k]:
			return False
	return True

def dfsearch(ts, words, found=[], depth_limit=None):
	'''Depth first search'''
	for w in words:
		if subset(words[w], ts):
			new_ts = Counter(ts - words[w])
			new_found = found + [w]
			if new_ts:
				if len(new_found) != depth_limit:
					yield from dfsearch(new_ts, words, new_found, depth_limit)
			else:
				yield frozenset(new_found)

if __name__ == '__main__':
	if len(sys.argv) == 3:
		depth_lim = int(sys.argv[2])
	else:
		depth_lim = None

	# First, get the target string
	target = sys.argv[1].replace(' ', '') # Remove spaces
	ts = frozenset(target)
	print('Letter set', ts)
	# Then, read the words, filtering the one that can't help
	with open('./italia-1a') as fp:
		words = {}
		for r in fp:
			w = r.strip()
			if len(w):
				ws = frozenset(w)
				wms = Counter(w)
				if ws <= ts:
					words[w] = wms
		print('Read dictionary, found', len(words), 'good words')

	# Depth first search
	anagrams = set(sol for sol in dfsearch(Counter(target), words, depth_limit=depth_lim))

	print('Found', len(anagrams))
	if input('Print them all? [y/N] ').strip() == 'y':
		for a in anagrams:
			print(a)