# Generating the set of all strings within a fixed edit distance of a initial string?

Provided a starting string initialString, and a particular alphabet of allowed characters {"A","B","C","D","E",...}, how can I generate the set of all strings such that EditDistance[initialString,setElement] = k, where k is specified as desired? How can I do the same if I only consider HammingDistance?

Rather, I should say, how do we do the above without generating all of the Tuples of relevant length, then checking each one for EditDistance or HammingDistance, which is probably the most naive way to proceed?

Here's a partial example of that naive strategy (partial because for EditDistance we need to generate tuples of the string length of the initial string $\pm \space k$):

k = 1;

stringTestLength = 8;

alphabet = {"0", "1", "R"};

tuples = Map[StringJoin, Tuples[alphabet, stringTestLength]];

testString = "00000000"

distanceOneList = {};
editDistanceCounter = 0;
For[i = 1, i <= Length[tuples], i++,
If[EditDistance[tuples[[i]], testString] == k,
editDistanceCounter += 1;
distanceOneList = Append[distanceOneList, tuples[[i]]];
];
];

distanceOneList
editDistanceCounter


The output here is of course the following length sixteen array:

{"00000001", "0000000Q", "00000010", "000000Q0", "00000100", "00000Q00", "00001000", "0000Q000", "00010000", "000Q0000", "00100000", "00Q00000", "01000000", "0Q000000", "10000000", "Q0000000"};


The "real" answer for EditDistance is 1 (for the length 7 tuple set) + 19 (for the length 9 tuple set) + 16 (for the length 8 = length of the initial string) tuple set. Thus, there are 36 strings over this alphabet within EditDistance k = 1 of the initial string "00000000".

kAwayWordsF[str_, dist_, alph_, strlen_] := Module[{len = StringLength[str], dict},
dict = StringJoin /@ Tuples[alph, strlen];
With[{nf = Nearest[dict]},
Complement[nf[str, {Infinity, dist}], nf[str, {Infinity, dist - 1}]]]]
kAwayWordsF["00000000",1,{"0","1","Q"},8]
(* {"00000001", "0000000Q", "00000010", "000000Q0", "00000100", "00000Q00", "00001000",
"0000Q000", "00010000", "000Q0000", "00100000", "00Q00000", "01000000", "0Q000000",
"10000000","Q0000000"} *)
kAwayWordsF["00000000",2,{"0","1","Q"},7]
(* {"0000001", "000000Q", "0000010", "00000Q0", "0000100", "0000Q00","0001000",
"000Q000", "0010000", "00Q0000", "0100000", "0Q00000","1000000", "Q000000"}  *)


Update: Removing the restriction that target strings have the same string length as the teststring:

distKWordsF[str_, dist_, alph_] := Module[{len = StringLength[str], dict},
dict = StringJoin /@ Join @@ (Tuples[alph, #] & /@ Range[len - dist, len + dist]);
With[{nf = Nearest[dict]},
Complement[nf[str, {Infinity, dist}], nf[str, {Infinity, dist - 1}]]]]
distKWordsF["00000000", 1, {"0", "1", "Q"}]
(*{"0000000","000000000","000000001","00000000Q","00000001","000000010",
"0000000Q","0000000Q0", "00000010","000000100","000000Q0","000000Q00",
"00000100", "000001000","00000Q00","00000Q000","00001000","000010000",
"0000Q000","0000Q0000","00010000","000100000","000Q0000","000Q00000",
"00100000","001000000", "00Q00000","00Q000000","01000000","010000000","0Q000000",
"0Q0000000","10000000","100000000","Q0000000","Q00000000"}*)
(Length@distKWordsF["00000000", #, {"0", "1", "Q"}]) & /@ {1, 2, 3, 4, 5}
(*{{36,472,3740,22096,110036}*)

• Great! So this is for the HammingDistance case. Is there a way to get Nearest to work for EditDistance? – Cray Apr 20 '14 at 11:00
• @Cray, this is for the EditDistance b/c the default DistanceFunction for Nearest with string data is EditDistance. – kglr Apr 20 '14 at 11:14
• Ah, I see, see we just need to join / concatenate the answers for $\pm k$ length strings, no? – Cray Apr 20 '14 at 11:15
• Not sure how to deal with HammingDistance. First, DistanceFunction option is available only for the two-argument input pattern for Nearest; the syntax Nearest[data, DistanceFunction->sth] does not work, so we need to use the form to map Nearest[data,#,DistanceFunction->sth]& to the list of target strings (and this is much slower than the approach nf=Nearest[data]; nf/@targetlist. Second, HammingDistance only works for strings with equal stringlengths ... – kglr Apr 20 '14 at 11:40
• ... Regarding "joining answers for +-k length strings", I don't think it would work (EditDistance is always less than or equal to HammingDistance) – kglr Apr 20 '14 at 11:41