This program shows different methods for generating anagrams which should be (somewhat) easy to solve. The methods are:
n-step method: for each turn, transpose two letters within a maximal distance, where the n in n-step is the maximum step to use, e.g. 1 or 2 to get easy solving anagrams.
generate anagrams of a word in some way (e.g. n-step method or simply shuffle the letters in the word), and then sort the word according to the best n-gram distance.
generate the anagrams in some way and sort them according to edit distance, see below.
n-gram distance
The n-gram distance compares the n-grams from the original word with the n-gram for the anagramated (shuffled) word. The more corresponding n-grams, the better. For both words it uses all possible n-grams, from 2-gram to (length word -1)-ngram. E.g. for the word anagram the n-grams used is "an", "na", ""ag", "gr", "ra", "am", "ana", "nag", ... "gram", "anag", ... "gram", "anagr","nagr". The distance is defined as: the number of n-grams that are the same (as the original word) divided by maximal number of n-grams for the word. This means that the distance may be from 0 (no likeness between the words at all) to 1 (same word).
Edit distance
The (Levenshtein) edit distance is a common metric for comparing the distance between two words, i.e. how similiar the are. It seems that this metric is not very good for comparing how well we recognize the word (i.e. solve the anagram), but this notion is just subjective findings and hold no scientific bearing.
Shuffling
Please note that the (random) shuffling part make take some time. The number of shuffled words is 500.
Note: This program was announced at my (swedish) blog: Skapa enkla anagram, where there may be some more info.
Result
Word: establishment Max steps: 1 Random word: no
n-step Method
Result by n-step method. This is for max step = 1. Showing the first 20 words.
The number and charactes in parenthesis is the specific steps. (5 <-> 6 : f <-> l edit dist: 2 ngram dist: 0.39 pct same positions: 0.79)
means that the 5'th and 6'th characters we transposed, which was the letter "f" and "l". The edit distance was 2 and ngram distance 0.39, and has 79% characters in the same positions as the source word.
establihsment (8 <-> 7 : s <-> h edit dist: 2 ngram dist: 0.35 pct same positions: 0.85)
esatblihsment (3 <-> 2 : t <-> a edit dist: 4 ngram dist: 0.13 pct same positions: 0.69)
esatblihsmnet (11 <-> 10 : e <-> n edit dist: 6 ngram dist: 0.05 pct same positions: 0.54)
seatblihsmnet (0 <-> 1 : s <-> e edit dist: 6 ngram dist: 0.04 pct same positions: 0.38)
seatblihsment (10 <-> 11 : e <-> n edit dist: 4 ngram dist: 0.12 pct same positions: 0.54)
seatblishment (7 <-> 8 : s <-> h edit dist: 2 ngram dist: 0.46 pct same positions: 0.69)
seatblishemnt (10 <-> 9 : m <-> e edit dist: 4 ngram dist: 0.14 pct same positions: 0.54)
seatblishemtn (12 <-> 11 : n <-> t edit dist: 4 ngram dist: 0.13 pct same positions: 0.38)
esatblishemtn (1 <-> 0 : s <-> e edit dist: 4 ngram dist: 0.14 pct same positions: 0.54)
esatblishemtn (12 <-> 12 : n <-> n edit dist: 4 ngram dist: 0.14 pct same positions: 0.54)
esatblsihemtn (7 <-> 6 : i <-> s edit dist: 6 ngram dist: 0.03 pct same positions: 0.38)
esatblsiehmtn (9 <-> 8 : h <-> e edit dist: 6 ngram dist: 0.04 pct same positions: 0.31)
esatblsiehmnt (12 <-> 11 : t <-> n edit dist: 5 ngram dist: 0.05 pct same positions: 0.46)
esatlbsiehmnt (5 <-> 4 : b <-> l edit dist: 5 ngram dist: 0.04 pct same positions: 0.31)
esatblsiehmnt (5 <-> 4 : l <-> b edit dist: 5 ngram dist: 0.05 pct same positions: 0.46)
seatblsiehmnt (0 <-> 1 : s <-> e edit dist: 5 ngram dist: 0.04 pct same positions: 0.31)
saetblsiehmnt (2 <-> 1 : e <-> a edit dist: 5 ngram dist: 0.04 pct same positions: 0.31)
saetbsliehmnt (5 <-> 6 : s <-> l edit dist: 5 ngram dist: 0.04 pct same positions: 0.23)
seatbsliehmnt (2 <-> 1 : a <-> e edit dist: 5 ngram dist: 0.04 pct same positions: 0.23)
Edit distance sort
The words generated by n-step method sorted by (Levenshtein) edit distance. Showing the first (best) 20 words which the edit distance for the anagram. Also: "step pos" is the position in the generated n-step word, i.e. in what turn that anagram was generated. "ngram dist" is the ngram distance (see above).
The words generated by the n-step method, sorted by ngram-distance (see above), showing the best 20 words. The ngram distance is also shown.
Also shows the edit distance and the position of the word in the generation of n-step anagrams.
seatblishment: 0.46 (edit dist: 2 step pos: 6)
establihsment: 0.35 (edit dist: 2 step pos: 1)
seatblishemnt: 0.14 (edit dist: 4 step pos: 7)
esatblishemtn: 0.14 (edit dist: 4 step pos: 10)
seatblishemtn: 0.13 (edit dist: 4 step pos: 8)
esatblihsment: 0.13 (edit dist: 4 step pos: 2)
sbestalimenht: 0.13 (edit dist: 4 step pos: 63)
esntisablthme: 0.12 (edit dist: 6 step pos: 184)
seatblihsment: 0.12 (edit dist: 4 step pos: 5)
estnisabtlhme: 0.10 (edit dist: 7 step pos: 181)
enstsibltahme: 0.09 (edit dist: 7 step pos: 193)
esntisbtalhme: 0.09 (edit dist: 7 step pos: 188)
esntsibltahme: 0.09 (edit dist: 7 step pos: 192)
sentbstailmeh: 0.09 (edit dist: 7 step pos: 209)
sbetalsimenth: 0.09 (edit dist: 4 step pos: 67)
esntisabtlhme: 0.09 (edit dist: 7 step pos: 182)
sebstalimenht: 0.09 (edit dist: 5 step pos: 62)
tsenisbtahmel: 0.08 (edit dist: 8 step pos: 169)
esntisbatlhme: 0.08 (edit dist: 7 step pos: 187)
esntisbalthme: 0.08 (edit dist: 7 step pos: 185)
estnisabthlme: 0.08 (edit dist: 7 step pos: 180)
tsenistbahmel: 0.08 (edit dist: 7 step pos: 168)
Shuffle method
The shuffle method just creates 500 random anagrams (permutations) based on the word. Here they are sorted by edit distance (see above), showing the first (best) 20 words .
bsnaeleshmitt: 6 (ngram distance: 0.05)
mtablessheint: 6 (ngram distance: 0.12)
estmalbsihnet: 6 (ngram distance: 0.04)
eltsasmenthbi: 6 (ngram distance: 0.08)
itablesemshtn: 6 (ngram distance: 0.10)
sabiehlesntmt: 6 (ngram distance: 0.04)
elestbasintmh: 6 (ngram distance: 0.05)
eseanlshbmitt: 6 (ngram distance: 0.03)
snabtilsmeteh: 6 (ngram distance: 0.03)
esmetblnshita: 6 (ngram distance: 0.06)
teahbistmensl: 6 (ngram distance: 0.06)
metenlstabish: 6 (ngram distance: 0.14)
netsbisehmlat: 6 (ngram distance: 0.03)
esaltshbmtein: 6 (ngram distance: 0.03)
nbhetaleismst: 6 (ngram distance: 0.04)
etaslimbtensh: 6 (ngram distance: 0.05)
lisehmentbtsa: 6 (ngram distance: 0.17)
etaisslmbnthe: 6 (ngram distance: 0.04)
istnlehmetsba: 6 (ngram distance: 0.06)
thlanetissmeb: 7 (ngram distance: 0.03)
nhtsetabsemli: 7 (ngram distance: 0.05)
lmenttbaihess: 7 (ngram distance: 0.09)
The same shuffled words as above, but now sorted by ngrams distance. Showing the first (best) 20 words. Also the edit distance and ngram distance is shown.