{"id":18268,"date":"2020-07-15T10:42:39","date_gmt":"2020-07-15T17:42:39","guid":{"rendered":"https:\/\/www.kith.org\/words\/?p=18268"},"modified":"2020-07-14T20:01:38","modified_gmt":"2020-07-15T03:01:38","slug":"algorithm-for-finding-anagrams","status":"publish","type":"post","link":"https:\/\/www.kith.org\/words\/2020\/07\/15\/algorithm-for-finding-anagrams\/","title":{"rendered":"Algorithm for finding anagrams"},"content":{"rendered":"\r\n

I was playing a word game (Capitals, an iOS app that\u2019s apparently no longer available), and I got to wondering how one would go about using a computer to find all the words that you can make with a given set of letters.<\/p>\r\n

I wouldn\u2019t use<\/em> such a program for playing a game. But I was curious about what the algorithm would be.<\/p>\r\n

In case I didn\u2019t describe the goal clearly above, the idea is essentially the same as what a Scrabble app would need to be able to do to come up with words to play: take a set of n<\/i> letters, and find all the words (in a given dictionary\/word list) that are n<\/i> or fewer letters long and that use only the given letters. If there are two Bs in the set of letters, then the words listed by the algorithm shouldn\u2019t contain more than two Bs. And so on.<\/p>\r\n

I thought briefly about how I would go about writing a program to do this, but I didn\u2019t get very far. My best guesses about how to approach it seemed like they would execute painfully slowly.<\/p>\r\n

So I went and looked around online, and of course Stack Overflow has some answers:<\/p>\r\n

Given a dictionary and a list of letters find all valid words that can be built with the letters<\/a>.<\/p>\r\n

I\u2019m not sure that I entirely follow the details of all the answers given there, but I\u2019m fairly confident that I could figure them out in detail if I had to.<\/p>\r\n

But one thing that the answers there don\u2019t explicitly say is that the pre-processing of the dictionary only has to be done once, and then you can use the pre-processed dictionary as many times as you want. Which, I\u2019m guessing, explains how internet Scrabble-word-finder sites operate: they\u2019ve already done the pre-processing, so they can use the processed dictionary to quickly find all the anagrams of a given set of letters (and all subsets of that set).<\/p>\r\n\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":5,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[110,101,41,81],"tags":[],"class_list":["post-18268","post","type-post","status-publish","format-standard","hentry","category-letters","category-anagrams","category-games","category-software"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.kith.org\/words\/wp-json\/wp\/v2\/posts\/18268","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.kith.org\/words\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kith.org\/words\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kith.org\/words\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kith.org\/words\/wp-json\/wp\/v2\/comments?post=18268"}],"version-history":[{"count":1,"href":"https:\/\/www.kith.org\/words\/wp-json\/wp\/v2\/posts\/18268\/revisions"}],"predecessor-version":[{"id":18269,"href":"https:\/\/www.kith.org\/words\/wp-json\/wp\/v2\/posts\/18268\/revisions\/18269"}],"wp:attachment":[{"href":"https:\/\/www.kith.org\/words\/wp-json\/wp\/v2\/media?parent=18268"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kith.org\/words\/wp-json\/wp\/v2\/categories?post=18268"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kith.org\/words\/wp-json\/wp\/v2\/tags?post=18268"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}