There are correct answers here, which heavily utilize python with it's magical functions that do almost everything for you. I will try to explain things with math and algorithms, so that you can apply it to any language you want.
So you have an alphabet {a1, a2, ... a_a}
(the cardinality of a
)in your case {'A', 'C', 'G', 'T'}
and the cardinality is 4. You have a string of length k
and you want to generate all the strings whose hamming distance is less or equal to d
.
First of all how many of them do you have? The answer does not depend on the string you select. If you selected a sting, you will have C(d, k)(a-1)^d
strings of which have a hamming distance d
from your string. So total number of strings is:
It rises exponentially in terms of almost every parameter, so you will not have any sort of fast algorithm to find all the words.
So how would you derive an algorithm that will generate all the strings? Notice that it is easy to generate a string which is at most one hamming distance away from your wold. You just need to iterate over all characters in the string and for each character try each letter in the alphabet. As you will see, some of the words would be the same.
Now to generate all the strings that are two hamming distances away from your string you can apply the same function that generate one hamming distance words for each word in the previous iteration.
So here is a pseudocode:
function generateAllHamming(str string, distance int):
alphabet = ['A', ...]// array of letters in your alphabet
results = {} // empty set that will store all the results
prev_strings = {str} // set that have strings from the previous iterations
// sets are used to get rid of duplicates
if distance > len(str){ distance = len(str)} // you will not get any new strings if the distance is bigger than length of the string. It will be the same all possible strings.
for d = 0; d < distance; d++ {
for one_string in prev_strings {
for pos = 0; pos < len(one_string); pos++ {
for char in alphabet {
new_str = substitute_char_at_pos(one_string, char, pos)
add new_str to set results
}
}
}
populate prev_strings with elements from results
}
return your results
}