CSC148H5 Lecture Notes - Lecture 9: Insertion Sort, Bubble Sort, Selection Sort
Document Summary
We"re interested in the e ciency for large problems. Two words are anagrams if the letters of one word can be rearranged to be the letters of the other word. horse and shore are anagrams. Are these? bill, lib deposit, topside march, charm sport, torts tra c, tra c. Given a word, suppose that we want to generate all anagrams of that word. An anagram of word w is a rearrangement of the letters of w that appear in the wordlist. For example, seohr is not an anagram of horse, because seohr isn"t in the wordlist. We could start with our word and nd all of its permutations. Six permutations: dog, dgo, odg, ogd, gdo, god. In general, if you agave a word of length n, there are n! permutations. Generate all n! (factorial) permutations and then check them all. Let"s say that our word is of length n, and that there are w words in the wordlist.
