Find all strings at distance k The edit (or Levenshtein) distance between two strings is the minimal number of single character insertions, deletions and substitutions needed to transform one string into the other.

The challenge is to write code to output all strings with edit distance exactly k from a fixed string of length 10, where k is a variable set in your code as is the fixed string.   The alphabet is 0 or 1. To test, take

1111011010


as the fixed string. The twist is that you can't output the same string twice.

You may not use any library or built in functions that compute the Levenshtein distance for you.

Score

This is a standard code-golf challenge. You can assume k will be a one-digit number.

Reference Implementation

(added by Martin Büttner)

For reference, here is a Mathematica solution (which isn't valid, due to use of EditDistance) which can be used to check results for correctness:

s = "1111011010";
k = 2;
Union @ Cases[
     Join @@ Array[# &lt;&gt; "" &amp; /@ {"0", "1"}~Tuples~# &amp;, 2 k + 1, 10 - k],
     x_ /; x~EditDistance~s == k
]


For the first ten values of k I the following results:

 k | # of results

 0              1
 1             28
 2            302
 3           1652
 4           5533
 5          14533
 6          34808
 7          80407
 8         180663
 9         395923
Scala 168 228

My first submission had a bug where it didn't consider multiple insertions at the same point in the input string.

After

val k = 1
val s = "1111011010"


The code that counts is:

def e(k:Int,s:String):Set[String]=if(k&lt;1)Set(s)else e(k-1,s).flatMap(e=&gt;"01"map(_+e))++(if(s=="")Set()else e(k,s.tail).map(s.head+_)++e(k-1,s.tail).flatMap(e=&gt;(Set("0","1","")-(s take 1))map(_+e)))
print(e(k,s))


To run, save both sections together as a file and run like:

$ scala distancek.scala
Set(111111010, 111101010, 1111001010, 11110011010, 1101011010, 11101011010, 111101101, 111101100, 11111011010, 1111011011, 1111011000, 11110101010, 1111010010, 11110110110, 11110110101, 111101110, 11110110010, 0111011010, 1110011010, 11110110100, 10111011010, 11011011010, 01111011010, 1011011010, 1111111010, 111011010, 11110111010, 1111011110)
$


Recursive function to build the edited strings. k is the number of edits remaining, s is the string to edit. Slightly ungolfed:

def e(k:Int,s:String):Set[String]=
  if(k&lt;1) Set(s)                           // No edits left
  else e(k-1,s).flatMap(e=&gt;"01"map(_+e))++ // Insert a character, consume an edit, continue from the same point
      (if(s=="") Set()                     // We're at the end of the string so only insertions are allowed
       else e(k,s.tail).map(s.head+_)++    // skip past this character, making no edit
       e(k-1,s.tail).flatMap(e=&gt;(Set("0","1","")-(s take 1))map(_+e))) // replace this character with its inverse or ""


Note that each step makes at least one of k, s smaller so we're guaranteed to terminate.



First submission (Incorrect)

print((0 to 10).permutations.flatMap{i=&gt;((s.map(_+""):+"")zip i).:\(Set("")){case((s,i),a)=&gt;a.flatMap{a=&gt;(if(i&lt;k)Set(1+s,0+s,"","0","1")-s else Set(s))map(_+a)}}}toSet)


We take the permutations of 0..10 and zip them with the word s + a terminal "" (for insertions at the end).
All the positions &lt; k are positions where an edit should occur. For each edit we replace the string at that position with

Set(1+s,0+s,"","0","1")-s # don't count substituting s for itself as an edit.


and finally convert to a set to remove duplicates.