Generation of a Hamming Series

Question

I have been trying to solve a programming problem, one of the modules of which requires me to generate Hamming sequences. The function takes input two numbers first a binary number N and another a decimal number K. It should now generate all possible numbers having a Hamming distance of up to K from N.

It would be really helpful if you provide me with an algorithm about how to solve this problem.

Thanks in advance.

Answer 1

The algorithm is pretty simple. You just need to chose all possible binary numbers contains from 0 to K ones. And then xor it with N, just like this:

    public static Char[] Xor(Char[] a, Char[] b)
    {
        Char[] c = new Char[a.Length];
        for (Int32 i = 0; i < a.Length; ++i)
            if (a[i] == b[i])
                c[i] = '0';
            else
                c[i] = '1';

        return c;
    }

    public static void Generate(Char[] original, Char[] current, int position, int k)
    {
        if (position == original.Length)
        {
            Console.WriteLine(Xor(original, current));
            return;
        }

        if (k > 0)
        {
            current[position] = '1';
            Generate(original, current, position + 1, k - 1);
        }

        current[position] = '0';
        Generate(original, current, position + 1, k);
    }

    // Find all Number with hamming distance up to 2 from 01100
    Generate("01100".ToCharArray(), "00000".ToCharArray(), 0, 2);

Note: count of numbers that have Hamming distance up to K from N can be extremely big, as soon it exponentially grows depend on value of K.

Answer 2

You can generate all number with K bits set by starting at (1<<K)-1 and applying NextPermutation until you've had them all.
XOR all those numbers with N.

Answer 3

A very simple approach (since you didn't mention something about performance) is to iterate through 1 to p and bitwise xor it with N if the number has less than K bits set as 1. p has the same bit length as N.

Pseudo code:

for i in [0..p]
   if countBits(i) <= K then
      result.add(p xor N)
   end
end

Answer 4

Isn't this for Interview Street? They ask you not to get others to do the problems for you.