jamie vs jon

jamievsjon.py

#!/usr/bin/env python
# encoding: utf-8
"""
jamiesort.py

Created by jonchui on 2011-11-23.
Copyright (c) 2011 __MyCompanyName__. All rights reserved.
"""

import sys
import os
from time import time as t
from time import sleep as s

'''
	Accepts a string. 
	Returns a list of all permutations of the string using all
characters.  
'''
def permute (word):
	retList=[]
	if len(word) == 1:
		# There is only one possible permutation
		retList.append(word)
	else:
		# Return a list of all permutations using all characters
		for pos in range(len(word)):
			# Get the permutations of the rest of the word 
			permuteList=permute(word[0:pos]+word[pos+1:len(word)])
			# Now, tack the first char onto each word in the list
			# and add it to the output
			for item in permuteList:
				retList.append(word[pos]+item)
	return retList


''' 
hash the words
permuate the testWord
lookup in hash
'''
def jons(words, testWord):
	d = {}
	for x in words:
		d[x] = 1
	return [x for x in permute(testWord) if x in d]

def qsort(L):
	if len(L) <= 1: return L
	return qsort( [ lt for lt in L[1:] if lt < L[0] ] )  +  [ L[0] ]  +  qsort( [ ge for ge in L[1:] if ge >= L[0] ] )

def qsortString(s):
	return ''.join(qsort(s))

# IMHO this is almost as nice as the Haskell version from www.haskell.org:
# qsort [] = [] 
# qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
#				 where 
#				   elts_lt_x = [y | y <- xs, y < x] 
#				   elts_greq_x = [y | y <- xs, y >= x]

'''
loop through list & qsort
each word, if length same, check if equal to our word
'''

def jamies(words, testWord):
	anagrams = []
	testWordSorted = qsortString(testWord)
	for x in words:
		if len(x) == len(testWord) and qsortString(x) == testWordSorted:
			anagrams.append(x)
	return anagrams
	
jonsCache = {}
jamiesCache = {}


def main():
	words = [x.strip('\n') for x in open('/usr/share/dict/words').readlines()]
	testWord = 'dog'
	print 'permutations of {0}'.format(testWord)
	t1 = t()
	a = jons(words,testWord)
	t2 = t()
	b = jamies(words,testWord)
	t3 = t()
	#assert a==b
	print 'jons: {0}\njamies:{1}'.format(a,b)
	print 'jons:  {0}\njamies: {1}'.format(t2-t1, t3-t2)
	
	testNumberOfWords(words,10)
	
def testNumbx`erOfWords(words,numberOfWords=100, start=100):
	jamiestime = 0
	jonstime = 0
	largeWords = words[start:start+numberOfWords]
	length = len(largeWords)
	print 'comparing list of short {0} words '.format(length)
	for x in largeWords:
		t1 = t()
		a = jons(words,x)
		t2 = t()
		b = jamies(words,x)
		t3 = t()
		jonstime+=(t2-t1)
		jamiestime+=(t3-t2)
	print 'jons:  {0}\njamies: {1}'.format(jonstime, jamiestime)


if __name__ == '__main__':
	main()

permutations of dog
jons: ['dog', 'god']
jamies:['dog', 'god']
jons: 0.0874760150909
jamies: 0.0546960830688
comparing list of short 10 words
jons: 29.8427231312
jamies: 4.77383542061