How do I create subset words for an anagram application (php)?

Question

I created an anagram creating application, by creating an anagram field in my database, with a lower cased alphabetically stored string.

For example, suction becomes cinostu, ear becomes aer, and so on.

What I want to do now is create sub words from the original anagram searched for.

Example: How would you go about pulling the subset words from a search for 'arrest', i.e. 'rest' and 'stare'.

Answer 1

Here's an approach I've used before that makes use of your list of alphabetically-sorted words.

1) Take your target word (arrest) and sort it (aerrst).

2) Then from the sorted word generate new strings where each letter is either included or excluded. For a word of N letters this gives 2**N possible strings. (I don't know PHP but can give you pseudocode or eg Python if you would like.)

For your target word we have: a, e, r, r, s, t, st, rs, rt, rst, rr, rs, rt, rst, rrs, rrt, rrst, er, er, es, et, est, ers, ert, erst, err, ers, ert, erst, errs, errt, errst, ae, ar, ar, as, at, ast, ars, art, arst, arr, ars, art, arst, arrs, arrt, arrst, aer, aer, aes, aet, aest, aers, aert, aerst, aerr, aers, aert, aerst, aerrs, aerrt, aerrst

3) Then check these strings against your sorted list. Those that appear in your sorted list correspond to the subset words you want.

eg aerrst corresponds to full anagrams (arrest, rarest, raster, ...)
eg aerst will be in your sorted list (stare, tears, ...)
eg rrs will not be in your sorted list

Answer 2

Include a space on the end of the original word. Each iteration where the space ends up in the middle of letters, you'll get two words. Then you can test those two words. If the space is on the beginning or end of the iteration pattern, trim it off and test that one word.