Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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]]];


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".

share|improve this question
up vote 1 down vote accepted
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}]]]]   
(* {"00000001", "0000000Q", "00000010", "000000Q0", "00000100", "00000Q00", "00001000",
    "0000Q000", "00010000", "000Q0000", "00100000", "00Q00000", "01000000", "0Q000000",
    "10000000","Q0000000"} *)
(* {"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"}]
    "0000000Q","0000000Q0", "00000010","000000100","000000Q0","000000Q00",
    "00000100", "000001000","00000Q00","00000Q000","00001000","000010000",
   "00100000","001000000", "00Q00000","00Q000000","01000000","010000000","0Q000000",
(Length@distKWordsF["00000000", #, {"0", "1", "Q"}]) & /@ {1, 2, 3, 4, 5}
share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.