Dear All, I am learning about analysis of algorithms (python 2.7.6). I am reading a book (Problem solving with Algorithms and Data Structures) where Python is the language used for implementations. The author introduces algorithm analysis in a clear and understandable way, and uses an anagram detection program as a template to compare different runtime implementations (quadratic, log linear, linear). In the linear, and most efficient implementation, the code is as follows (comments added by me):
def anagram_test2(s1,s2):""" Checks if two strings are anagrams of each other Runs with O(n) linear complexity """ if (not s1) or (not s2): raise TypeError, "Invalid input: input must be string" return None # Initialize two lists of counters c1 = [0] * 26 c2 = [0] * 26 # Iterate over each string# When a char is encountered, # increment the counter at # its correspoding position for i in range(len(s1)): pos = ord(s1[i]) - ord("a") c1[pos] += 1 for i in range(len(s2)): pos = ord(s2[i]) - ord("a") c2[pos] += 1 j = 0 hit = Truewhile j < 26 and hit: if c1[j] == c2[j]: j += 1 else: hit = False return hit My questions are: 1) Is it computationally more/less/equally efficient to use an explicit while loop as it is to just do "return c1 === c2" (replacing the final code block following the two for loops). I realize that this single line of code performs an implicit for loop over each index to test for equality. My guess is that because in other languages you may not be able to do this simple test, the author wanted to present an example that could be adapted for other languages, unless the explicit while loop is less expensive computationally. 2) How could I go about adapting this algorithm for multiple strings (say I had 20 strings and wanted to check if they are anagrams of one another). def are_anagrams(*args): """ Accepts a tuple of strings and checks if they are anagrams of each other """ # Check that neither of strings are null for i in args: if not i: raise TypeError, "Invalid input" return None # Initialize a list of counters for each string c = ( [] for i in range(len(args) ) ??? Many thanks in advance! _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor